ACM-ICPC 2018 徐州赛区网络预赛

Diposting di | Edited on

传送门

A. Hard to prepare

题意

一个环形的 n 的列表每个数都是 0 到 2^k-1，求相邻两个数同或不为 0 的方案数。同或 ->相同为1，不同为0

思路

利用环形涂色的公式，稍微改改

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
//const ll inf=0x3f3f3f3f3f3f3f3fLL;
const int inf=500;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
#define pp pair<int,int>
int n,m,l,k;
char s[4];
int flag[11];
ll kk=1;
ll dp[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        kk=1;
        for(int i=1;i<=k;i++){
            kk=(kk*2)%mod;
        }
        ll l=(kk-1+mod)%mod;///在一个N-2个格子环中加入一个格子的种类数即An-2 * (M-1)
        ll r=(kk-2+mod)%mod;///
        dp[1]=kk;
        dp[2]=(dp[1]*l)%mod;
        for(int i=3;i<=n;i++){
            dp[i]=((dp[i-2]*l)%mod+((dp[i-1]-dp[1]+mod)%mod*(r)%mod)%mod)%mod;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}

B. BE, GE or NE

题意

两人博弈，每人轮流选择可以 +ai 或 −bi 或 ∗(−1)，两个人分别要最终大于或小于某个数，值不能超过100，和少于-100，奇数A选，偶数B选。求结果。

思路

记忆化搜索，状态是 (当前轮次, 当前分数)。注意数组的下标不能为负数 所以值都+200

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
//const ll inf=0x3f3f3f3f3f3f3f3fLL;
const int inf=500;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
#define pp pair<int,int>
int n,m,l,k;
int dp[1010][600];
int a[1010],b[1010],c[1010];
int dfs(int i,int value){
  //  cout<<"i=="<<i<<endl;
    if(i>n)return value-200;///超界限
    if(dp[i][value]!=500)return dp[i][value];///走过了
   // cout<<"lai"<<endl;
    if(i&1){///男生
       // cout<<"我是男生"<<endl;
        int now=value-200;///变成正常的
        int ans=-200;///最低值
        if(a[i]>0){
           int k=min(100,now+a[i]);   ///保证不超出去
           int kk=dfs(i+1,k+200);  ///探寻下一个
            ans=max(ans,kk);
        }
        if(b[i]>0){
           int k=max(-100,now-b[i]);///最小的
           int kk=dfs(i+1,k+200);
            ans=max(ans,kk);
        }
        if(c[i]==1){ ///
            int kk=dfs(i+1,-now+200);
            ans=max(ans,kk);
        }
        dp[i][value]=ans;
    }
    else{//女生
        int now=value-200;
        int ans=200;
        if(a[i]>0){
           int k=min(100,now+a[i]);
           int kk=dfs(i+1,k+200);
            ans=min(ans,kk);
        }
        if(b[i]>0){
           int k=max(-100,now-b[i]);
           int kk=dfs(i+1,k+200);
            ans=min(ans,kk);
        }
        if(c[i]==1){
            int kk=dfs(i+1,-now+200);
            ans=min(ans,kk);
        }
        dp[i][value]=ans;
    }
    return dp[i][value];
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m>>k>>l;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    for(int i=0;i<=1005;i++)
    for(int j=0;j<=500;j++)dp[i][j]=500;
    int anw=dfs(1,m+200);
    if(anw>=k)cout<<"Good Ending"<<endl;
    else if(anw<=l)cout<<"Bad Ending"<<endl;
    else cout<<"Normal Ending"<<endl;
    return 0;
}

F. Features Track

题意

每帧出现一对数字，求一对数字连续出现的最长帧数。

思路

这题读半天都没懂题意，读懂之后直接map+pair

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
#define pp pair<int,int>
char s[1100000];
int a[1100000];
map<pp,int>flag;
map<pp,int>sum;
map<pp,int>now;
map<pp,int>anw;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int num=0;
        flag.clear();
        sum.clear();
        now.clear();
        anw.clear();
        for(int i=0;i<n;i++){
            int k;
            cin>>k;
            now.clear();
            for(int j=0;j<k;j++){
                int a,b;
                cin>>a>>b;
                if(now[make_pair(a,b)]==0){
                    now[make_pair(a,b)]=1;
                    sum[make_pair(a,b)]++;
                    if(sum[make_pair(a,b)]>anw[make_pair(a,b)]){
                        anw[make_pair(a,b)]=sum[make_pair(a,b)];
                        if(anw[make_pair(a,b)]>num){
                            num=anw[make_pair(a,b)];
                        }
                    }
                }
            }
            for(auto k:sum){
                if(now[k.first]==0){
                    sum[k.first]=0;
                }
            }

        }
        cout<<num<<endl;
    }
    return 0;
}

G. Trace

题意

堆叠若干个以原点为左下角的矩形，求看得到的右边界和上边界的总长度。注意新的会覆盖久的，所以从后往前最好了

思路

分别对x和y 从后往前搞,如果 后面有小于当前值的 就用当前值减去最大的小于它的值，如果没有就直接加上。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
#define pp pair<int,int>
map<ll,int>mp;
ll a[55000],b[55000];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    map<ll,int>::iterator it;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    mp.clear();
    ll sum=0;
    for(int i=n-1;i>=0;i--){
        it=mp.lower_bound(a[i]);
        if(mp.empty()||it==mp.begin()){//如果找不到;
            sum+=a[i];
        }
        else{
            it--;
            sum+=(a[i]-it->first);
        }
        mp[a[i]]++;
    }
    mp.clear();
    for(int i=n-1;i>=0;i--){
        it=mp.lower_bound(b[i]);
        if(mp.empty()||it==mp.begin()){//如果找不到;
            sum+=b[i];
        }
        else{
            it--;
            sum+=(b[i]-it->first);
        }
        mp[b[i]]++;
    }
    cout<<sum<<endl;
    return 0;
}

H. Ryuji doesn’t want to study

题意

求

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define N 100005
typedef long long ll;
using namespace std;

ll tree[N<<3],lazy[N<<3],a[N],s[N];
ll n,m;
void pushup(ll rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void pushdown(ll len,ll rt){
    if(lazy[rt]){
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        tree[rt<<1]+=lazy[rt]*(len-len/2);
        tree[rt<<1|1]+=lazy[rt]*(len/2);
        lazy[rt]=0;
    }
}

void build(ll l,ll r,ll rt){
    lazy[rt]=0;
    if(l==r){
        tree[rt]=s[l];
        return;
    }
    ll mid=(l+r)/2;
    build(lson);
    build(rson);
    pushup(rt);
}

void add(ll L,ll R,ll k,ll l,ll r,ll rt){
    if(L<=l&&R>=r){
        tree[rt]+=(r-l+1)*k;
        lazy[rt]+=k;
        return;
    }
    pushdown(r-l+1,rt);
    ll mid=(l+r)/2;
    if(L<=mid) add(L,R,k,lson);
    if(R>mid) add(L,R,k,rson);
    pushup(rt);
}

long long query(ll L,ll R,ll l,ll r,ll rt){
    if(L<=l&&R>=r){
        return tree[rt];
    }
    pushdown(r-l+1,rt);
    ll mid=(l+r)/2;
    long long ans=0;
    if(L<=mid) ans+=query(L,R,lson);
    if(R>mid) ans+=query(L,R,rson);
    pushup(rt);
    return ans;
}

int main(){
    scanf("%lld %lld",&n,&m);
    a[0]=0;
    for(ll i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(ll i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
    }
    build(1,n,1);
    ll pos,x,y;
    ll ans,ans1,ans2;
    for(ll i=1;i<=m;i++){
        scanf("%lld %lld %lld",&pos,&x,&y);
        if(pos==1){
            ans1=query(x,y,1,n,1);
            if(x-1<1){
                ans2=0;
            }
            else {
                ans2=query(x-1,x-1,1,n,1);
            }
            ans2=ans2*(y-x+1);
            ans=ans1-ans2;
            printf("%lld\n",ans);
        }
        else{
            add(x,n,y-a[x],1,n,1);
            a[x]=y;
        }
    }

    return 0;
}
/*
6 100
1 2 5 7 3 4
1 3 5
2 4 6
1 3 5
2 3 7
1 1 6
2 3 6
1 1 4

*/

I. Characters with Hash

题意

温暖签到题,可是因为00这个数据变得不温暖QAQ

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
char s[1100000];
int a[1100000];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        char z;
        cin>>n>>z;
        cin>>s;
        int len=strlen(s);
        int num=0;
        int flag=0;
        for(int i=0;i<len;i++){
            a[i]=abs(z-s[i]);
            if(a[i]==0&&flag==0)continue;
            else if(a[i]>0&&a[i]<=9&&flag==0){
                num=1;
                flag=1;
                continue;
            }
            else{
                flag=1;
                num+=2;
            }
        }
        if(num==0)cout<<1<<endl;
        else
            cout<<num<<endl;
    }
    return 0;
}

J. Maze Designer

题意

一个N*M的矩形,每个格点到其邻近点的边有其权值,需要构建出一个迷宫,使得构建迷宫的边权之和最小,之后Q次查询,每次给出两点坐标,给出两点之间的最短路径

思路

队友结束后十分钟A的,打完之后我看了下大概是这样

可以把每个格点视作视作图的点,隔开两点的边视作图的边,则构建迷宫可以视作求其生成树,剩余的边就是组成迷宫的墙.因为要花费最小,所以使删去的墙权置最大即可,呢么就是求最大生成树即可.
然后每次查询相当于查这个最大生成树上任意两点的最短距离,到这一步就是个LCA板子题了.
所以:最大生成树+LCA

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define N 250500
#define MOD 1e9+7
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int fa[N];
struct sair{
    int x,y,v;
}A[750500];
struct ssair{
    int to,v;
};
vector<ssair>ve[N];
int depth[N];
int parent[N][25];
int gw[N][25];
int visit[N];
int n,m;
int MAX;

void dfs(int root,int pre,int d,int co){
	depth[root]=co;
	gw[root][0]=d;
	parent[root][0]=pre;
	visit[root]=1;
	for(int i=0;i<ve[root].size();i++){
		if(ve[root][i].to!=pre){
			dfs(ve[root][i].to,root,ve[root][i].v,co+1);
		}
	}
}

int lca(int u,int v){
	if(depth[u]<depth[v]){
		int t;
		t=u;
		u=v;
		v=t;
	}
	int ans=0;
	for(int k=0;k<=MAX;k++){
		if(((depth[u]-depth[v]) >> k) & 1){
			ans+=gw[u][k];
			u=parent[u][k];
		}
	}
	if(u==v){
		return ans;
	}
	for(int k=MAX;k>=0;k--){
		if(parent[u][k]!=parent[v][k]){
			ans+=gw[u][k];
			ans+=gw[v][k];
			u=parent[u][k];
			v=parent[v][k];
		}
	}
	ans+=gw[u][0];
	ans+=gw[v][0];
	return ans;
}

bool cmp(sair a,sair b){
    return a.v>b.v;
}

int Find(int x){
    int r=x;
    while(x!=fa[x]){
        x=fa[x];
    }
    int y;
    while(r!=x){
        y=fa[r];
        fa[r]=x;
        r=y;
    }
    return x;
}

int join(int x,int y){
    int xx=Find(x);
    int yy=Find(y);
    if(xx!=yy){
        fa[xx]=yy;
        return 1;
    }
    return 0;
}

int main(){
    std::ios::sync_with_stdio(false);
    int a,b;
    int q;
    char ch1,ch2;
    int m1,m2;
    cin>>n>>m;
    int sum=1;
    for(int i=1;i<=n*m+1;i++){
        fa[i]=i;
    }
    int co=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch1>>m1>>ch2>>m2;
            if(ch1=='D'){
                A[co].x=(i-1)*n+j,A[co].y=A[co].x+n,A[co].v=m1;
                co++;
            }
            if(ch2=='R'){
                A[co].x=(i-1)*n+j,A[co].y=A[co].x+1,A[co].v=m2;
                co++;
            }
        }
    }
    sort(A,A+co,cmp);
    ssair S,E;
    for(int i=0;i<co;i++){
        if(join(A[i].x,A[i].y)){
            sum++;
            S.to=A[i].y,S.v=1;
            E.to=A[i].x,E.v=1;
            ve[A[i].x].push_back(S);
            ve[A[i].y].push_back(E);
            if(sum==n*m){
                break;
            }
        }
    }
    dfs(1,0,0,0);
    MAX=int((log(n*m*1.0)/log(2*1.0)));
    for(int i=1;i<=MAX;i++){
        for(int j=1;j<=n*m;j++){
            if(parent[j][i-1]==0){
                parent[j][i]=0;
            }
            else{
                parent[j][i]=parent[parent[j][i-1]][i-1];
                gw[j][i]=gw[j][i-1]+gw[parent[j][i-1]][i-1];
        		//cout<<gw[gw[j][i-1]][i-1]<<"  "<<gw[j][i]<<"  hhh"<<endl;
            }

        }
    }
    cin>>q;
    int x1,y1,x2,y2;
    int xx,yy;
    while(q--){
        cin>>x1>>y1>>x2>>y2;
        xx=(x1-1)*n+y1;
        yy=(x2-1)*n+y2;
        printf("%d\n",lca(xx,yy));
    }
}