2017-2018 ACM-ICPC, Asia Daejeon Regional Contest(训练日常)

Posted on | In

感想

CF Rank: 60/273
emmmm这比赛的题非常友好啊？我们队5个小时没法摸鱼有题可做，A题好像是个树形dp，L是个枚举时间最短路？算了有空再补吧。。

Problem A Broadcast Stations

Unsolved

Problem B Connect3

Solved By shuzijun (+,4:08)

题意

给定一个4*4棋盘，黑色先手，且必须放在给定的(1,x)位置上，之后只有下面有棋子时，上面才能放棋子。比如放(3,1)时，(2,1),(1,1)都需要已经放过棋子。取胜的条件与井字棋类似，横，竖，斜有连续的三个就是胜利。要求你找出白色方最后一手放在(a,b)位置上就能取得胜利的不同的局面有多少种。

思路

暴搜即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
#define rush() int T;scanf("%d",&T);int kase=1;while(T--)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
const int maxn =2e6+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-10;
inline ll read(){ll ans=0,flag=1;char c;c=getchar();while(c<'0' || c>'9'){if(c=='-')flag=-1;c=getchar();}while(c>='0' && c<='9'){ans=ans*10+(ll)(c-'0');c=getchar();}return ans*flag;}
ll quickpow(ll x,ll y,ll mod){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

int mp[15][15];
map<int,int> vis;
int a,b,ans;

bool judge(int x)
{
    int cnt;
    for(int i=0;i<4;i++)
    {
        cnt=0;
        for(int j=0;j<4;j++)
        {
            if(mp[i][j]==x)
                cnt++;
            else cnt=0;
            if(cnt==3)
                return true;
        }
        cnt=0;
        for(int j=0;j<4;j++)
        {
            if(mp[j][i]==x)
                cnt++;
            else cnt=0;
            if(cnt==3)
                return true;
        }
    }
    if(mp[0][0]==x&&mp[0][0]==mp[1][1]&&mp[1][1]==mp[2][2])
        return true;
    if(mp[1][1]==x&&mp[1][1]==mp[2][2]&&mp[2][2]==mp[3][3])
        return true;
    if(mp[0][1]==x&&mp[0][1]==mp[1][2]&&mp[1][2]==mp[2][3])
        return true;
    if(mp[1][0]==x&&mp[1][0]==mp[2][1]&&mp[2][1]==mp[3][2])
        return true;
    if(mp[0][3]==x&&mp[0][3]==mp[1][2]&&mp[1][2]==mp[2][1])
        return true;
    if(mp[0][2]==x&&mp[0][2]==mp[1][1]&&mp[1][1]==mp[2][0])
        return true;
    if(mp[1][2]==x&&mp[1][2]==mp[2][1]&&mp[2][1]==mp[3][0])
        return true;
    if(mp[1][3]==x&&mp[1][3]==mp[2][2]&&mp[2][2]==mp[3][1])
        return true;
    return false;
}

int gethash()
{
    int res=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            res=res*3+mp[i][j];
        }
    }
    return res;
}

void dfs(int x)
{
    for(int j=0;j<4;j++)
    {
        for(int i=0;i<4;i++)
        {
            if(mp[i][j])
                continue;
            if(i&&!mp[i-1][j])
                continue;
            mp[i][j]=x;
            if(judge(x))
            {
                if(x==2&&i==a&&j==b)
                {
                    int now=gethash();
                    if(!vis[now])
                        vis[now]=true,ans++;
                }
                mp[i][j]=0;
                continue;
            }
            dfs(x==1?2:1);
            mp[i][j]=0;
        }
    }
}

int main()
{
    int x;
    while(cin>>x>>a>>b)
    {
        memset(mp,0,sizeof mp);
        ans=0;
        vis.clear();
        mp[0][x-1]=1;
        a--,b--;
        dfs(2);
        cout<<ans<<endl;
    }
    return 0;
}

Problem C Game Map

Solved By ManuShi (+,1:00)

题意

给定一张无向图，定义一种合法路径为路径上后一个点的度数严格大于前一个点的度数。为长度最长的合法路径长度是多少

思路

对度数排序，从度数小的点往度数大的点更新即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const int MAXN=100005,MAXM=600005;
vector<int> G[MAXN];
int deg[MAXN],ans[MAXN];
struct node{
    int id,deg;
}N[MAXN];
bool cmp(node n1,node n2){
    return n1.deg<n2.deg;
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int u,v;
        ms(deg,0),ms(ans,0);
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
            deg[u]++,deg[v]++;
            N[u].deg++,N[v].deg++;
        }
        for(int i=0;i<n;i++)N[i].id=i;
        sort(N,N+n,cmp);
        int maxs=0;
        for(int i=0;i<n;i++){
            int now=N[i].id;
            for(int j=0;j<G[now].size();j++){
                int go=G[now][j];
                if(deg[go]>deg[now]){
                    ans[go]=max(ans[go],ans[now]+1);
                    maxs=max(ans[go],maxs);
                }
            }
        }
        printf("%d\n",maxs+1);
        for(int i=0;i<MAXN;i++)G[i].clear();
    }
    return 0;
}

Problem D Happy Number

Solved By ManuShi (+1,00:23)

题意

定义f(x)为各位数字的平方的和。如果多次操作能变成1，那么就是happy number，不然就不是happy number

思路

初始数字为1,000,000,000，但是注意到平方的和最多也就81*9，开个1000的数组判判有没有循环就行

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

int vis[1005];
int getsum(int n){
    int sum=0;
    while(n){
        int num=n%10;
        sum+=num*num;
        n/=10;
    }
    return sum;
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    int n;
    while(~scanf("%d",&n)){
        ms(vis,0);
        int now=getsum(n);
        while(now!=1&&!vis[now]){
            vis[now]=1;
            now=getsum(now);
        }
        if(now==1)printf("HAPPY\n");
        else printf("UNHAPPY\n");
    }
    return 0;
}

Problem E How Many to Be Happy?

Upsolved By ManuShi

题意

问对于每条边来说，让其变成图的最小生成树中的边最少需要移走几条边，输出求和后的答案

思路

若要使得该边在最小生成树中，我们要保证u,v的两端的子图不能通过其他比当前边小的边来联通，也就是我们要求的答案即是图中比当前边长度小的所有边所构成图的最小割（边容量为1）。所以考虑枚举所有边，以图中比当前边长度小的所有边来建图，以边的端点为源点汇点跑最大流。好像是是2.5*10^9的算法啊，怎么跑的这么快

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const int MAXN=105,MAXM=2005;
int n,m;
int head[MAXN],nxt[MAXM],cap[MAXM],to[MAXM],edgecnt;
void addedge(int u,int v,int w){
    to[edgecnt]=v;
    cap[edgecnt]=w;
    nxt[edgecnt]=head[u];
    head[u]=edgecnt++;
}
int level[MAXN],cur[MAXN];
void bfs(int u){
    ms(level,-1);
    level[u]=0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=head[now];~i;i=nxt[i]){
            int v=to[i];
            if(cap[i]>0&&level[v]<0){
                level[v]=level[now]+1;
                q.push(v);
            }
        }
    }
}
int dfs(int u,int t,int f){
    if(u==t)return f;
    for(int &i=cur[u];~i;i=nxt[i]){
        if(cap[i]>0&&level[to[i]]>level[u]){
            int d=dfs(to[i],t,min(f,cap[i]));
            if(d>0){
                cap[i]-=d;
                cap[i^1]+=d;
                return d;
            }
        }
    }
    return 0;
}
int dinic(int s,int t){
    int flow=0;
    while(1){
        int f;
        bfs(s);
        for(int i=0;i<=n;i++)cur[i]=head[i];
        if(level[t]<0)return flow;
        while((f=dfs(s,t,INTINF))>0){
            flow+=f;
        }
    }
}

struct edge{
    int u,v,w;
    edge(){}
    edge(int u,int v,int w):u(u),v(v),w(w){}
}E[MAXM];

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    while(~scanf("%d%d",&n,&m)){
        int u,v,w;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&w);
            E[i]=edge(u,v,w);
        }
        int ans=0;
        for(int i=0;i<m;i++){
            ms(head,-1);
            edgecnt=0;
            for(int j=0;j<m;j++){
                if(i!=j&&E[i].w>E[j].w){
                    addedge(E[j].u,E[j].v,1);
                    addedge(E[j].v,E[j].u,0);
                    addedge(E[j].v,E[j].u,1);
                    addedge(E[j].u,E[j].v,0);
                }
            }
            ans+=dinic(E[i].u,E[i].v);
        }
        printf("%d\n",ans);
    }
    return 0;
}

Problem F Philosopher’s Walk

Solved By shuzijun (+2,02:12)

题意

边长都是2的k次幂，每个正方形都是前面4个拼接而成（具体见题目图片）。从左下角开始走，给定步数len和k，问走len步最后位置的坐标

思路

这题是shuzijun写的我思路也不是太确定，理论上来说因为正方形的放置方法是固定的，那么我们可以考虑递归，dfs要判断正方形是如何放置的，然后返回一个偏移量累加应该就可以了。。吧？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<bits/stdc++.h>
#define rush() int T;scanf("%d",&T);int kase=1;while(T--)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
const int maxn =2e3+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-10;
inline ll read(){ll ans=0,flag=1;char c;c=getchar();while(c<'0' || c>'9'){if(c=='-')flag=-1;c=getchar();}while(c>='0' && c<='9'){ans=ans*10+(ll)(c-'0');c=getchar();}return ans*flag;}
ll quickpow(ll x,ll y,ll mod){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

int ans[maxn][maxn];

void dfs(int flag,int n,int m,int &posx,int &posy)
{
    if(n==2)
    {
        if(flag==1)
        {
            if(m==2)
                posy=posy+1;
            else if(m==3)
            {
                posx=posx+1;
                posy=posy+1;
            }
            else if(m==4)
                posx=posx+1;
        }
        else if(flag==2)
        {
            if(m==4)
                posy=posy+1;
            else if(m==3)
            {
                posx=posx+1;
                posy=posy+1;
            }
            else if(m==2)
                posx=posx+1;
        }
        else if(flag==3)
        {
            if(m==2)
                posx=posx-1;
            else if(m==3)
            {
                posx=posx-1;
                posy=posy-1;
            }
            else if(m==4)
                posy=posy-1;
        }
        else if(flag==4)
        {
            if(m==4)
                posx=posx-1;
            else if(m==3)
            {
                posx=posx-1;
                posy=posy-1;
            }
            else if(m==2)
                posy=posy-1;
        }
        return;
    }
    int num=(m-1)/(n*n/4)+1;
    if(flag==1)
    {
        if(num==1)
            flag=2;
        else if(num==2)
        {
            flag=1;
            posy=posy+n/2;
            m-=(n*n/4);
        }
        else if(num==3)
        {
            flag=1;
            posx=posx+n/2;
            posy=posy+n/2;
            m-=(n*n/2);
        }
        else
        {
            flag=3;
            posx=posx+n-1;
            posy=posy+n/2-1;
            m-=(n*n/4*3);
        }
    }
    else if(flag==2)
    {
        if(num==1)
            flag=1;
        else if(num==2)
        {
            flag=2;
            posx=posx+n/2;
            m-=(n*n/4);
        }
        else if(num==3)
        {
            flag=2;
            posx=posx+n/2;
            posy=posy+n/2;
            m-=(n*n/2);
        }
        else
        {
            flag=4;
            posx=posx+n/2-1;
            posy=posy+n-1;
            m-=(n*n/4*3);
        }
    }
    else if(flag==3)
    {
        if(num==1)
            flag=4;
        else if(num==2)
        {
            flag=3;
            posx=posx-n/2;
            m-=(n*n/4);
        }
        else if(num==3)
        {
            flag=3;
            posx=posx-n/2;
            posy=posy-n/2;
            m-=(n*n/2);
        }
        else
        {
            flag=1;
            posx=posx-n/2+1;
            posy=posy-n+1;
            m-=(n*n/4*3);
        }
    }
    else
    {
        if(num==1)
            flag=3;
        else if(num==2)
        {
            flag=4;
            posy=posy-n/2;
            m-=(n*n/4);
        }
        else if(num==3)
        {
            flag=4;
            posx=posx-n/2;
            posy=posy-n/2;
            m-=(n*n/2);
        }
        else
        {
            flag=2;
            posx=posx-n+1;
            posy=posy-n/2+1;
            m-=(n*n/4*3);
        }
    }
    dfs(flag,n/2,m,posx,posy);
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int posx=1,posy=1;
        int flag=1;
        dfs(flag,n,m,posx,posy);
        cout<<posx<<' '<<posy<<endl;
    }
    return 0;
}

Problem G Rectilinear Regions

Solved By ManuShi (+1,04:30)

题意

给定两根直线（具体见题目中图片），问蓝色在红色上面时交的面积有多少，求个数和面积和

思路

题目表示拐点坐标两两不同，大力扫描线就完事了，注意两边非封闭区域面积不计

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

struct point{
    ll x,y,id;
    bool operator <(const point &p1)const{
        return x<p1.x;
    }
}P[50005];

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int cnt=0,lastx;
        ll ay,by;
        scanf("%I64d",&ay);
        for(int i=0;i<n;i++){
            scanf("%I64d%I64d",&P[cnt].x,&P[cnt].y);
            P[cnt++].id=0;
        }
        scanf("%I64d",&by);
        for(int i=0;i<m;i++){
            scanf("%I64d%I64d",&P[cnt].x,&P[cnt].y);
            P[cnt++].id=1;
        }
        sort(P,P+cnt);
        int flag=by>ay?0:2;
        //1 blue up,2 red up,1 start,2 end
        ll area=0,tarea=0,num=0;
        for(int i=0;i<cnt;i++){
            if(flag==0){
                if(P[i].id==1&&P[i].y<ay){
                    flag=2;
                    by=P[i].y;
                }
                else if(P[i].id==1)by=P[i].y;
                else if(P[i].id==0&&P[i].y>by){
                    flag=2;
                    ay=P[i].y;
                }
                else if(P[i].id==0)ay=P[i].y;
            }
            else if(flag==1){
                if(P[i].id==1&&P[i].y>ay){
                    area+=(P[i].x-lastx)*(by-ay);
                    tarea+=(P[i].x-lastx)*(by-ay);
                    by=P[i].y,lastx=P[i].x;
                }
                else if(P[i].id==1&&P[i].y<ay){
                    flag=2;
                    area+=(P[i].x-lastx)*(by-ay);
                    tarea=0;
                    by=P[i].y;
                    num++;
                }
                else if(P[i].id==0&&P[i].y<by){
                    area+=(P[i].x-lastx)*(by-ay);
                    tarea+=(P[i].x-lastx)*(by-ay);
                    ay=P[i].y,lastx=P[i].x;
                }
                else if(P[i].id==0&&P[i].y>by){
                    flag=2;
                    area+=(P[i].x-lastx)*(by-ay);
                    tarea=0;
                    ay=P[i].y;
                    num++;
                }
            }
            else if(flag==2){
                if(P[i].id==1&&P[i].y>ay){
                    flag=1;
                    by=P[i].y,lastx=P[i].x;
                }
                else if(P[i].id==1){
                    by=P[i].y;
                }
                else if(P[i].id==0&&P[i].y<by){
                    flag=1;
                    ay=P[i].y,lastx=P[i].x;
                }
                else if(P[i].id==0){
                    ay=P[i].y;
                }
            }
        }
        printf("%I64d %I64d\n",num,area-tarea);
    }
    return 0;
}

Problem H Rock Paper Scissors

Solved By ManuShi (+,02:04)

题意

给定两个石头剪刀布序列，问怎么放第二个序列能使赢得次数尽可能多，最多是多少。

思路

刚做过字符串循环匹配就给我来这个=_=，显然这个题常规的字符串数据结构是搞不了的（因为它有可能不是完全匹配的啊，常规数据结构只能算完全匹配的算不了匹配了几个）。那么考虑反转第二个字符串，然后对3种字符分别使用fft匹配。卷积形式为A[j]*B[i-j],我们每次设要匹配的字符为1，不要的为0，这样只有1*1时才会对答案有贡献，这样最后乘积c[i]就是我们要的每个位置的匹配个数。FFT以后对答案求和取个最大值就行

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const int MAXN=262145;//1<<n
const double PI=acos(-1);
struct Complex{
    double real,image;
    Complex(){real=0,image=0;}
    Complex(double real){this->real=real,image=0;}
    Complex(double real,double image){this->real=real,this->image=image;}
    Complex operator +(const Complex &c){
        return Complex(c.real+real,c.image+image);
    }
    Complex operator -(const Complex &c){
        return Complex(real-c.real,image-c.image);
    }
    Complex operator *(const Complex &c){
        return Complex(c.real*real-c.image*image,c.real*image+c.image*real);
    }
    Complex operator *(double x){
        return Complex(real*x,image*x);
    }
    Complex operator /(double x){
        return Complex(real/x,image/x);
    }
    Complex rev(){
        return Complex(real,-image);
    }
};
void fft(Complex *a, int n,Complex *com) {
	int k = 0;
	while ((1 << k)<n)k++;
	for (int i = 0;i<n;i++) {
		int t = 0;
		for (int j = 0;j<k;j++)if (i&(1 << j))t |= (1 << (k - j - 1));
		if (i<t)swap(a[i], a[t]);
	}
	for (int l = 2;l <= n;l *= 2) {
		int m = l / 2;
		for (Complex *p = a;p<a + n;p += l) {
			for (int i = 0;i<m;i++) {
				Complex t = com[n / l*i] * p[m + i];
				p[m + i] = p[i] - t;
				p[i]=p[i]+t;
			}
		}
	}
}
Complex omega[MAXN], iomega[MAXN];
void init(int n) {
	for (int i = 0;i<n;i++) {
		omega[i] = Complex(cos(2 * PI / n*i), sin(2 * PI / n*i));
		iomega[i] = omega[i].rev();
	}
}
void dft(Complex *a, int n) {
	fft(a, n,omega);
}
void idft(Complex *a, int n) {
	fft(a, n,iomega);
	for (int i = 0;i<n;i++)a[i] =a[i]/ n;
}
Complex a[MAXN], b[MAXN],c[MAXN];
int A[MAXN],B[MAXN];
int ans[MAXN];
char strb[MAXN],stra[MAXN];
char win[3];
int getFlag(char ch){
    for(int i=0;i<3;i++){
        if(win[i]==ch)return i+1;
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    int n,m;
    win[0]='R',win[1]='S',win[2]='P';
    while(~scanf("%d%d",&n,&m)){
        ms(A,0),ms(B,0),ms(ans,0);
        scanf("%s",strb);
        scanf("%s",stra);
        int len=1;
        while(len<(m+n))len<<=1;
        init(len);
        for(int w=0;w<3;w++){
            int go=(w+1)%3+1;
            for(int i=0;i<n;i++){
                if(getFlag(strb[i])==go)B[i]=1;
                else B[i]=0;
            }
            for(int i=0;i<m;i++){
                if(getFlag(stra[i])==w+1)A[m-i-1]=1;
                else A[m-i-1]=0;
            }
            for(int i=0;i<len;i++)a[i]=Complex(A[i],0),b[i]=Complex(B[i],0);
            dft(a,len),dft(b,len);
            for(int i=0;i<len;i++)c[i]=a[i]*b[i];
            idft(c,len);
            for(int i=m-1;i<len;i++){
                ans[i]+=(int)(c[i].real+0.5);
            }
        }
        int maxs=-1;
        for(int i=0;i<len;i++){
            maxs=max(maxs,ans[i]);
        }
        printf("%d\n",maxs);
        //for(int i=0;i<n;i++)if()
    }
    return 0;
}

Problem I Slot Machines

Solved By Shuzijun (+2,03:24)

题意

给定一个序列，要求找到以k开始，p为循环节的循环部分并且要求p+k最小

思路

反转字符串跑getNext，循环节就是i-next[i]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define rush() int T;scanf("%d",&T);int kase=1;while(T--)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
const int maxn =2e6+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-10;
inline ll read(){ll ans=0,flag=1;char c;c=getchar();while(c<'0' || c>'9'){if(c=='-')flag=-1;c=getchar();}while(c>='0' && c<='9'){ans=ans*10+(ll)(c-'0');c=getchar();}return ans*flag;}
ll quickpow(ll x,ll y,ll mod){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

int next1[maxn];
int p[maxn];
int n;

void getNext()
{
    next1[0]=-1;
    int k=-1;
    int j=0;
    while(j<=n)
    {
        if(k==-1||p[j]==p[k])
        {
            k++;
            j++;
            /*if(p[j]!=p[k])*/
            next1[j]=k;
            /*else next1[j]=next1[k];*/
        }
        else k=next1[k];
    }
}

int main()
{
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
            p[i]=read();
        memset(next1,0,sizeof next1);
        reverse(p,p+n);
        getNext();
        int ans=INF;
        int l=0,c=n;
        for(int i=1;i<=n;i++)
        {
            int nc=i-next1[i];
            int nl=n-i;
            if(nc+nl<ans)
            {
                l=nl,c=nc,ans=nc+nl;
            }
            else if(nc+nl==ans&&nc<c)
            {
                l=nl,c=nc,ans=nc+nl;
            }
        }
        cout<<l<<' '<<c<<endl;
    }
    return 0;
}

Problem J Strongly Matchable

Unsolved

Problem K Untangling Chain

Solved By ManuShi (+,02:49)

题意

给定一个操作序列，每个操作(a,b)a代表走a，b代表走完a后接下来向左向右。让你重设a使得所有线段不相交

思路

维护当前走过的minx,miny,maxx,maxy。显然走到这样一个长方形外面下步往左往右都不会碰到，可以理解为一圈一圈往外跑

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const int MAXN=10005;
int dir[MAXN];

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    int n;
    while(~scanf("%d",&n)){
        int num;
        int maxx=0,minx=0,maxy=0,miny=0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&num,&dir[i]);
        }
        //0->right,1->down,2->left,3->up
        int now=0,nowx=0,nowy=0;
        for(int i=0;i<n;i++){
            if(i)printf(" ");
            switch(now){
            case 0:
                printf("%d",maxx-nowx+1);
                nowx=maxx+1;
                maxx=nowx;
                break;
            case 1:
                printf("%d",nowy-miny+1);
                nowy=miny-1;
                miny=nowy;
                break;
            case 2:
                printf("%d",nowx-minx+1);
                nowx=minx-1;
                minx=nowx;
                break;
            case 3:
                printf("%d",maxy-nowy+1);
                nowy=maxy+1;
                maxy=nowy;
                break;
            }
            if(dir[i]==1){
                now=(now-1+4)%4;
            }
            else if(dir[i]==-1){
                now=(now+1)%4;
            }
        }
        printf("\n");
    }
    return 0;

Problem L Vacation Plans

Unsolved