2018-2019 ICPC SWERC 2018
in GYM训练 with 0 comment

2018-2019 ICPC SWERC 2018

in GYM训练 with 0 comment

A.City of Lights

zyj (00:13:06) +0

题意

有一排灯,给出k个操作,每个操作给出一个x,要你把$x,2*x,3*x,...$反转,问你所有时刻最多多少灯灭

题解

签到题,模拟即可

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,k,a[maxn];
int main(){
    scanf("%d%d",&n,&k);
    int ans=0;
    rep(i,1,k){
        int x;scanf("%d",&x);
        for(int j=x;j<=n;j+=x) a[j]^=1;
        int tmp=0;
        rep(j,1,n) tmp+=a[j];
        ans=max(ans,tmp);
    }
    printf("%d\n",ans);
}

B.Blurred Pictures

wrf(01:16:01)+2

题意

给出一个 01 矩阵,该矩阵每行只有一个区间为 1。对每行给出这个区间,求整个矩阵的最大全 1 子正方形。
矩阵边长不超过 $10^5$。

题解

做法

枚举每一行作为底边,对于第i行,二分边长x,用 ST 表查询行号[i-x+1,i]中的最大左端点和最小右端点。如果这一区间大于等于x,则是一合法正方形,更新答案。

时间复杂度

$O(n \log^2 n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

ll st1[N][21];

void init1(ll* a,int n)
{
    for(int i=1;i<=n;i++)
    {
        st1[i][0]=*(a+i);
    }
    for(int j=1;j<=21;j++)
    {
        for(int i=1;i+(1<<j)-1<=N;i++)
        {
            st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
        }
    }
}
ll query1(int l,int r)
{
    int k=log2(r-l+1);
    return max(st1[l][k],st1[r-(1<<k)+1][k]);
}


ll st2[N][21];

void init2(ll* a,int n)
{
    for(int i=1;i<=n;i++)
    {
        st2[i][0]=*(a+i);
    }
    for(int j=1;j<=21;j++)
    {
        for(int i=1;i+(1<<j)-1<=N;i++)
        {
            st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
        }
    }
}
ll query2(int l,int r)
{
    int k=log2(r-l+1);
    return min(st2[l][k],st2[r-(1<<k)+1][k]);
}


ll a[N],b[N];

bool check(int x,int n)
{
    int l=query1(n-x+1,n),r=query2(n-x+1,n);

    return r-l+1>=x;
}

int main(void)
{    
    int n=read();
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();

    init1(a,n);
    init2(b,n);

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=i+1;
        int mid;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(check(mid,i)) l=mid;
            else r=mid;
        }

        ans=max(ans,l);
    }

    printf("%d",ans);
    
    return 0;
}

C.Crosswords

zyj (04:53:53) +1

题意

给出一个$N \times M$的网格$(N,M \leq 4)$,然后给出A个长为n的字符串和B个长为m的字符串,问你有多少种方案满足:选一些A中的字符串放入表格中中,使得表中也能构造出某些B的字符串,反之亦然;

题解

由于题目里说了单词全部由字典给出,换句话说就是数据随机,那么直接DFS暴搜既可,理论复杂度$O(min(A,B)^{max(n,m)})$

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
char s[maxn][4],c[10];
int nxt[maxn][27],pos[5],ans,tot,A,B,n,m;
void update(){
    int len=strlen(c),now=0;
    rep(i,0,len-1){
        if(!nxt[now][c[i]-'a']) nxt[now][c[i]-'a']=++tot;
        now=nxt[now][c[i]-'a'];
    }
}
void dfs(int cnt,int pos[]){
    if(cnt==m){ans++;return;}
    int tmp[5];
    rep(i,1,A){
        int flag=1;
        rep(j,0,n-1){
            if(!nxt[pos[j]][s[i][j]-'a']){flag=0;break;}
            tmp[j]=nxt[pos[j]][s[i][j]-'a'];
        }
        if(flag) dfs(cnt+1,tmp);
    }
} 
int main(){
    scanf("%d%d%d%d",&n,&A,&m,&B);
    if(A<=B){
        rep(i,1,A) scanf("%s",s[i]);
        rep(i,1,B) scanf("%s",c),update();
    }
    else{
        rep(i,1,A) scanf("%s",c),update();
        rep(i,1,B) scanf("%s",s[i]);
        swap(n,m);swap(A,B);
    }
    dfs(0,pos);
    printf("%d\n",ans);
}

D.Monument Tour

lmj (01:44:05) +0

题意

$x*y$的二维坐标轴上,有n个点,要选择一个点y,使得只能在该纵坐标上往右走,上下可以随便走,要求经过所有的点,求最小的长度。

题解

对于每一列,显然只和最大值最小值有关,使用一个队列和一个优先队列,开始将所有点按照y最小值从小到大排序存入队列,优先队列按照y最大值从小到大排序,枚举选的行,将y大于等于该行的点从队列删除加入优先队列,同时将优先队列中y大于该行的删除,同时记录数量,那么对于第一个队列中的点,往下移会使得所需要的长度减少,对于从优先队列中删掉的点,会使得长度增加,对于优先队列中的点不变。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct node
{
    int minn,maxx;
}a[N];
bool cmp(node x ,node y)
{
    if(x.minn!=y.minn)return x.minn<y.minn;
    else return x.maxx<y.maxx;
}
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        a[i].minn=m+1;
        a[i].maxx=-1;
    }
    int qy;
    scanf("%d",&qy);
    ll sum=0;
    ll ans=0;
    for(int i=1;i<=qy;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].minn=min(a[x].minn,y);
        a[x].maxx=max(a[x].maxx,y);
        //printf("------%d %d %d\n",x,a[x].minn,a[x].maxx);
    }
    sort(a,a+n,cmp);
    queue<node>q;
    for(int i=0;i<n;i++){
        if(a[i].minn!=m+1){
            //printf("%d %d %d\n",i,a[i].minn,a[i].maxx);
            q.push(a[i]);
            sum+=a[i].maxx;
        }
    }
    ans=sum;
    priority_queue<paii,vector<paii>,greater<paii> >qu;
    while(!q.empty()&&q.front().minn==0){
        paii tmp;
        tmp.fr=q.front().maxx;
        tmp.sc=q.front().minn;
        qu.push(tmp);
        q.pop();
    }
    ll cnt=0;
    for(int i=1;i<=m;i++){
        sum-=q.size();
        while(!q.empty()&&q.front().minn==i){
            paii tmp;
            tmp.fr=q.front().maxx;
            tmp.sc=q.front().minn;
            qu.push(tmp);
            q.pop();
        }
        while(!qu.empty()&&qu.top().fr<i){
            //printf("%d\n",qu.top().fr);
            qu.pop();
            cnt++;
        }
        sum+=cnt;
        //printf("--%d %lld\n",i,sum);
        ans=min(ans,sum);
    }
    printf("%lld\n",ans*2+(n-1));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Rounding

lmj (00:52:14) +3

题意

给定n个概率四舍五入后的结果(四舍五入前和为100),求这n个概率可能的最大值和最小值,如果不可能出现一个满足的条件输出IMPOSSIBLE

题解

对于每个点求其的最小值,只要将其他点都设为最大(+0.49),此时就可以得到最小值(注意该最小值可能不能四舍五入得到给出的答案,那么无解),对于最大值,将其他点设为最小值(-0.50),求此时的最大值,注意最大值不能小于最小值,同时要特殊判断有些点概率为0的情况。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
string b[N];
void work()
{
    int n;
    cin>>n;
    double sum=0;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>b[i]>>a[i];
        sum+=a[i];
        if(a[i]==0)cnt++;
    }
    double minn=sum+(n-1)*0.49-100;
    if(minn<-0.5){
        printf("IMPOSSIBLE\n");return;
    }
    minn=min(0.5,minn);
    double maxx=100-(sum-(n-cnt-1)*0.5);
    double maxx2=100-(sum-(n-cnt)*0.5);
    maxx=min(maxx,0.49);
    maxx2=min(maxx2,0.49);
    if(-minn>maxx){
        printf("IMPOSSIBLE\n");return;
    }
    for(int i=1;i<=n;i++){
        cout<<b[i];
        if(a[i]!=0){
            printf(" %.2f %.2f\n",max(a[i]-minn,0.0),max(a[i]+maxx,0.0));
        }else{
            printf(" %.2f %.2f\n",max(a[i]-minn,0.0),max(a[i]+maxx2,0.0));
        }
 
    }
}
int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Paris by Night

wrf(04:56:58)+1

题意

平面上有若干个带权的点,求一条经过其中任意两点的直线,使得直线左右两侧总权值(均包括线上两点)的差的绝对值最小。
保证三点不共线。点数不超过 $10^5$

题解

做法

首先枚举其中一点,将其变换到原点。
对其他点进行极角排序,通过双指针枚举可能同时处于一侧的区间,统计答案。

时间复杂度

$O(n^2\log n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

vector<pair<ll,ll> > v,d,tv;
vector<pair<int,ll> > s;

int pos(ll x,ll y)
{
    if(x>0 && y>=0) return 1;
    if(x<=0 && y>0) return 2;
    if(x<0 && y<=0) return 3;
    if(x>=0 && y<0) return 4;
    return 0;
}

bool cmp(const pair<int,ll> l,const pair<int,ll> r)
{
    return 
    pos(tv[l.first].first,tv[l.first].second)==pos(tv[r.first].first,tv[r.first].second)?
    tv[l.first].second*tv[r.first].first<tv[r.first].second*tv[l.first].first:
    pos(tv[l.first].first,tv[l.first].second)<pos(tv[r.first].first,tv[r.first].second);
}

bool cmp2(const pair<ll,ll>& l,const pair<ll,ll>& r)
{
    return pos(l.first,l.second)==pos(r.first,r.second)?l.second*r.first<r.second*l.first:pos(l.first,l.second)<pos(r.first,r.second);
}

int main(void)
{
    int n=read();

    v.resize(n);
    d.resize(n);
    s.resize(n);
    tv.resize(n);

    ll sum=0;

    for(int i=0;i<n;i++) scanf("%ld %ld %ld",&v[i].first,&v[i].second,&s[i].second),s[i].first=i,sum+=s[i].second;

    ll ans=sum;
    for(int x=0;x<n;x++)
    {
        for(int i=0;i<n;i++) tv[i].first=v[i].first-v[x].first,tv[i].second=v[i].second-v[x].second;
        sort(s.begin(),s.end(),cmp);

        vector<pair<ll,double> > tts(3*n+10);
        for(int i=1;i<n;i++)
        {
            tts[i].first=s[i].second;
            if(tv[s[i].first].second==0)
            {
                if(tv[s[i].first].first>0) tts[i].second=0.0;
                else tts[i].second=M_PI;
            }
            else tts[i].second=atan2(tv[s[i].first].second,tv[s[i].first].first);
            
            if(tv[s[i].first].second<0) tts[i].second+=M_PI*2;
            tts[i+n-1].first=tts[i].first;
            tts[i+2*n-2].first=tts[i].first;
            tts[i+n-1].second=tts[i].second+M_PI*2;
            tts[i+2*n-2].second=tts[i].second+M_PI*4;
        }

        for(int i=1;i<=3*n-3;i++){
            tts[i].first+=tts[i-1].first;
        }
        ll ts=0;
        int r=1;
        for(int l=1;l<n;l++)
        {
            while(tts[r+1].second-tts[l].second<=M_PI)
            {
                r++;
            }
            ll a=tts[r].first-tts[l].first;
            ll b=sum-s[0].second-s[l].second-a;
            
            ans=min(ans,abs(a-b));
        }
    }

    printf("%lld",ans);
    
    return 0;
}

G.Strings

题意

题解


H.Travel Guide

lmj (02:44:) +3

题意

以每个点到给定3个点的距离构成三元组,只要存在三元组使得该三元组三个都大于等于那个三元组(不能完全等于)时,将该三元组删去(如果不能到给定3个点的任意一个,那么一样也是删去),求最后会留下多少个点(给定的3个点同样也算在内)。

题解

用dij求出每个点的三元组之后,就是一个偏序问题,使用K-D tree(CDQ要写3个,挺难写的)解决即可。(K-D tree 模板太长了,加上其他代码有200行,就不放了)


I.Mason's Mark

zyj (03:42:46) +2

题意

给出字母A,B,C的表示形式,问你给定01图中三个字母的数量

题解

垃圾题,模拟即可!
注意$w$和$h$是$1e4$级别的,只能接受$O(w*h)$或者$O(w*h*log(w*h))$的复杂度,所以可以先dfs判一下连通块,再在块内判断,这样就能保证每个点只访问一次;


J.Mona Lisa

题意

题解


K.Dishonest Driver

wrf(00:44:16)+0

题意

给出一个字符串,每次可选择一个有完整循环节的子串,用它的完整循环节代替它(完整循环节定义为能整除串长的循环节)。求经过任意次操作后最小的串长。
串长不超过 700。

题解

做法

区间 dp。
首先预处理每个子串最小的完整循环节:
枚举作为完整循环节的子串[l,r],对每个位置i>r检测是否有c[i]=c[i-(r-l+1)],没有则跳出。如果此时同时子串长整除i-l+1,即证子串[l,i]存在完整循环节[l,r],记作f[i,j]=[l,r]
接下来是常规区间 dp 套路。对于每个区间[l,r],它可能被化为两个区间的和,也可能被化为它的最小完整循环节。我们就得出状态转移方程:

$$ dp_{i,j}=min\left\{ \begin{aligned} &min_k(dp_{i,k}+dp_{k+1,j}) \\ &dp_{f[i,j]} \end{aligned} \right. $$

照方程转移即可。

时间复杂度

两部分时间复杂度都是 $O(n^3)$,所以总时间复杂度为 $O(n^3)$。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=720;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

pair<int,int> f[N][N];
char c[N];
int dp[N][N];

int main(void)
{
    int n=read();
    scanf("%s",c+1);

    for(int l=1;l<=n;l++)
    {
        for(int r=l;r<=n;r++)
        {
            int len=r-l+1;
            for(int i=r+1;i<=n;i++)
            {
                if(c[i]!=c[i-len]) 
                {
                    break;
                }
                if((i-l+1)%len==0 && (f[l][i].second==0 || f[l][i].second-f[l][i].first>r-l)) f[l][i]={l,r};
            }
        }
    }

    for(int l=1;l<=n;l++)
    {
        for(int i=1;i+l-1<=n;i++)
        {
            dp[i][i+l-1]=l;
            if(f[i][i+l-1]!=pair<int,int>(0,0))
            {
                dp[i][i+l-1]=min(dp[i][i+l-1],dp[f[i][i+l-1].first][f[i][i+l-1].second]);
            }
            for(int k=i;k<i+l-1;k++)
            {
                dp[i][i+l-1]=min(dp[i][i+l-1],dp[i][k]+dp[k+1][i+l-1]);
            }
        }
    }

    printf("%d",dp[1][n]);
    
    return 0;
}

Responses