2015 CCPC 个人题解

---

title : 2015CCPC 个人题解
date : 2022-11-21
tags : ACM,题解，练习记录
author : Linno

---

2015 CCPC 个人题解

题目链接：https://codeforces.com/gym/103964

补题进度：8/12

A-Secrete Master Plan

只要判四个棋子旋转四次是否可以跟另一种摆放重合即可。

#include
#define int long long
using namespace std;

int a[5][5],b[5][5];

bool check(){
	if(a[0][0]!=b[0][0]) return false;
	if(a[1][0]!=b[1][0]) return false;
	if(a[0][1]!=b[0][1]) return false;
	if(a[1][1]!=b[1][1]) return false;
	return true;
}

void solve(){
	for(int i=0;i<=1;++i){
		for(int j=0;j<=1;++j){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<=1;++i){
		for(int j=0;j<=1;++j){
			cin>>b[i][j];
		}
	}
	int flag=0;
	for(int i=1;i<=5;++i){
		if(check()) flag=1;
		int T=a[0][0];
		a[0][0]=a[1][0];
		a[1][0]=a[1][1];
		a[1][1]=a[0][1];
		a[0][1]=T; 
	}
	if(flag) cout<<"POSSIBLE\n";
	else cout<<"IMPOSSIBLE\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int i=1;i<=T;++i){
		cout<<"Case #"<<i<<": ";
		solve();
	}
}
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

C-The Battle of Chibi

每次问长度为k的上升子序列有多少个，可以直接树状数组然后DP。

#include
//#define int long long
#define lb(x) (x&-x)
using namespace std;
typedef long long ll;
const int N=2007;
const ll mod=1e9+7;

inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}

int rx[N*N],ry[N*N],rz[N*N],top;

vector<int>vt;
int n,m,a[N],rk[N];
ll dp[N][N],tr[N][N<<1];
inline void update(int id,int x,int w){
	if(!x) return;
	for(;x<N;x+=lb(x)) tr[id][x]=(tr[id][x]+w+mod)%mod;
}

inline ll query(int id,int x){
	ll res=0;
	for(;x;x-=lb(x)) res=(res+tr[id][x])%mod;
	return res;
}

void solve(){
	vt.clear();top=0;
	n=read();m=read();
	vt.emplace_back(0);
	for(int i=1;i<=n;++i) a[i]=read(),vt.emplace_back(a[i]);
	sort(vt.begin(),vt.end());
	for(int i=1;i<=n;++i) rk[i]=lower_bound(vt.begin(),vt.end(),a[i])-vt.begin()+1;
	rk[0]=1;update(0,1,1);
	for(int i=1;i<=n;++i){
		for(int k=0;k<min(i,m);++k){
			dp[i][k+1]=(dp[i][k+1]+query(k,rk[i]-1))%mod;
			update(k+1,rk[i],dp[i][k+1]);
			++top;rx[top]=k+1;ry[top]=rk[i];rz[top]=dp[i][k+1];
		}
	}
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=dp[i][m],ans%=mod;
	for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) dp[i][j]=0;
	while(top){
		update(rx[top],ry[top],-rz[top]);
		--top;
	}update(0,1,-1);
	printf("%lld\n",ans);
}

signed main(){
	int T=1;
	T=read();
	for(int i=1;i<=T;++i){
		printf("Case #%d: ",i);
		solve();
	}
}
/*
3
3 2
1 2 3
3 2
3 2 1
5 2
1 2 1 2 3

3
8 2
42 42 50 10 89 98 12 4
4 2
77 55 95 35
3 2
15 27 85

*/
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

D-Pick The Sticks

可以转化为背包问题，$dp[i][j][0]$表示不放在边上，使用长度$j$的位置能在前$i$个中最高取得多少价值，同理，$dp[i][j][1]和dp[i][j][2]$分别表示把当前物品中心放在最左边和最右边的情况，第一维滚动掉，就可以了。然后要特判一根肯定是可以放的。

#include
#define int long long 
using namespace std;
const int N=4007;
int n,L,w[N],v[N],dp[N][5];

void solve(int t){
	cin>>n>>L;
	L<<=1;
	int ans=0;
	for(int i=1;i<=n;++i){
		cin>>w[i]>>v[i];
		ans=max(ans,v[i]); //至少能放一根上去 
		w[i]<<=1;
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;++i){
		for(int j=L;j>=0;--j){
			if(j>=w[i]){
				for(int k=0;k<=2;++k) dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+v[i]);
			}
			if(j>=w[i]/2){
				dp[j][2]=max(dp[j][2],dp[j-w[i]/2][1]+v[i]);
				dp[j][1]=max(dp[j][1],dp[j-w[i]/2][0]+v[i]);
			}
		}
	}
	for(int j=L;j>=0;--j){
		ans=max(ans,dp[j][0]);
		ans=max(ans,dp[j][1]);
		ans=max(ans,dp[j][2]);
	}
	cout<<"Case #"<<t<<": "<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int i=1;i<=T;++i){
		solve(i);
	}
	return 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
39
40
41
42
43
44
45

E-Ba Gua Zhen

找最大异或和回路，应该也是板子，使用高斯消元或者线性基都能做。

#include
#define int long long
#define pii pair<int,int>
#define mk make_pair
#define F first
#define S second 
using namespace std;
const int N=5e5+7;

vector<pii>G[N];
vector<int>ans;
int n,m,Xor[N],vis[N];

void dfs(int x,int f,int val){
	if(vis[x]){
		ans.emplace_back(val^Xor[x]);
		return;
	}
	vis[x]=1;
	for(auto p:G[x]){
		int to=p.F,w=p.S;
		if(to==f) continue;
		if(!vis[to]) Xor[to]=val^w;
		dfs(to,x,val^w);
	}
}

void solve(int t){
	cin>>n>>m;
	ans.clear();
	memset(vis,0,sizeof(vis));
	memset(Xor,0,sizeof(Xor));
	for(int i=1;i<=n;++i) G[i].clear();
	for(int i=1,u,v,w;i<=m;++i){
		cin>>u>>v>>w;
		G[u].emplace_back(mk(v,w));
		G[v].emplace_back(mk(u,w));
	}
	dfs(1,-1,0);
	int k=0,j;
	for(int i=60;i>=0;--i){
		for(j=k;j<ans.size();++j) if((ans[j]&(1ll<<i))!=0) break;
		if(j==ans.size()) continue;
		if(j!=k) swap(ans[k],ans[j]);
		for(j=k+1;j<ans.size();++j) if((ans[j]&(1ll<<i))!=0) ans[j]^=ans[k];
		++k;
	}
	int res=0;
	for(int i=0;i<k;++i) res=max(res,res^ans[i]);
	cout<<"Case #"<<t<<": "<<res<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int t=1;t<=T;++t){
		solve(t);
	}
	return 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

G-Ancient Go

直接枚举每一个o的位置，找其连通块，并记录这个连通块的气（就是围棋里还没堵住的位置），如果是1的话就能吃掉了。模拟即可。

#include
//#define int long long
using namespace std;

char mp[20][20];
int vis[20][20],ct[20][20],idx,res=0;

inline void check(int x,int y,int id){
	if(vis[x][y]||x<1||x>9||y<1||y>9) return;
	vis[x][y]=id;
	if(mp[x][y-1]=='o') check(x,y-1,id);
	if(mp[x][y+1]=='o') check(x,y+1,id);
	if(mp[x+1][y]=='o') check(x+1,y,id);
	if(mp[x-1][y]=='o') check(x-1,y,id);
	if(mp[x][y-1]=='.'&&!ct[x][y-1]) ct[x][y-1]=1,++res;
	if(mp[x][y+1]=='.'&&!ct[x][y+1]) ct[x][y+1]=1,++res;
	if(mp[x-1][y]=='.'&&!ct[x-1][y]) ct[x-1][y]=1,++res;
	if(mp[x+1][y]=='.'&&!ct[x+1][y]) ct[x+1][y]=1,++res;
}

void solve(){
	idx=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=9;++i){
		for(int j=1;j<=9;++j){
			cin>>mp[i][j];
		}
	}
	for(int i=0;i<=10;++i) mp[i][0]=mp[0][i]=mp[10][i]=mp[i][10]='x';
	for(int i=1;i<=9;++i){
		for(int j=1;j<=9;++j){
			res=0;
			if(!vis[i][j]&&mp[i][j]=='o'){
				memset(ct,0,sizeof(ct));
				check(i,j,++idx);
				if(res==1){
					cout<<"Can kill in one move!!!\n";
					return;
				}
			} 
		}
	}
	cout<<"Can not kill in one move!!!\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int i=1;i<=T;++i){
		cout<<"Case #"<<i<<": ";
		solve();
	}
}
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

H-Sudoku

直接暴力枚举答案，然后满足条件就跳出。

#include
#define int long long
#define pii pair<int,int>
#define mk make_pair
using namespace std;

char mp[5][5],tmp[5][5];
int visx[5][5],visy[5][5];
int num;
vector<pii>vt;

bool check(){
	for(int i=1;i<=4;++i){  //检查小格 
		for(int j=1;j<=4;j+=2){
			for(int k=1;k<=4;k+=2){
				if(tmp[j][k]==tmp[j][k+1]) return false;
				if(tmp[j][k]==tmp[j+1][k]) return false;
				if(tmp[j][k]==tmp[j+1][k+1]) return false;
				if(tmp[j+1][k]==tmp[j][k+1]) return false;
				if(tmp[j+1][k]==tmp[j+1][k+1]) return false;
				if(tmp[j][k+1]==tmp[j+1][k+1]) return false;
			}
		}
	}
	return true;
}

void dfs(int stp){
	if(stp==num){  //找到答案 
		if(!check()) return;
		for(int i=1;i<=4;++i){
			for(int j=1;j<=4;++j){
				cout<<tmp[i][j];
			}
			cout<<"\n";
		}
		return;
	}
	int x=vt[stp].first,y=vt[stp].second;
	for(int i=1;i<=4;++i){
		if(!visx[x][i]&&!visy[y][i]){
			visx[x][i]=1;visy[y][i]=1;
			tmp[x][y]=i+'0';
			dfs(stp+1);
			visx[x][i]=0;visy[y][i]=0;
		}
	}
}

void solve(){
	vt.clear();num=0;
	memset(visx,0,sizeof(visx));
	memset(visy,0,sizeof(visy));
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			cin>>mp[i][j];
			tmp[i][j]=mp[i][j];
		}
	}
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			if(mp[i][j]=='*'){
				++num;
				vt.emplace_back(mk(i,j));
			}else{
				visx[i][mp[i][j]-'0']=1;
				visy[j][mp[i][j]-'0']=1;
			}
		}
	}
	dfs(0);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int i=1;i<=T;++i){
		cout<<"Case #"<<i<<":\n";
		solve();
	}
}
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

K-Game Rooms

#include
#define int long long
using namespace std;
const int N=4007;

int pre[2][N],ppre[2][N],suf[2][N],ssuf[2][N];
int n,a[2][N],dp[2][N]; 

int calc(int l,int r,int f){ //cost函数 
	f^=1;
	int mid=((l+r)>>1);
	if(l==1&&r==n) return 0x3f3f3f3f3f3f3f3f;
	if(l==1) return ppre[f][r];
	if(r==n) return ssuf[f][l];
	int res=ssuf[f][l]-ssuf[f][mid+1]-(mid-l+1)*suf[f][mid+1];
	res+=ppre[f][r]-ppre[f][mid]-(r-mid)*pre[f][mid]; 
	return res;
}

void init(){
	memset(a,0,sizeof(a));
	memset(dp,0x3f,sizeof(dp));
	memset(pre,0,sizeof(pre));
	memset(suf,0,sizeof(suf));
	memset(ppre,0,sizeof(ppre));
	memset(ssuf,0,sizeof(ssuf));
}

void solve(int t){
	cin>>n;
	init();
	for(int i=1;i<=n;++i) cin>>a[0][i]>>a[1][i];
	dp[0][0]=dp[1][0]=0;
	for(int i=1;i<=n;++i){
		for(int k=0;k<=1;++k){
			pre[k][i]=pre[k][i-1]+a[k][i];
			ppre[k][i]=ppre[k][i-1]+pre[k][i];
		}
	}
	for(int i=n;i;--i){
		for(int k=0;k<=1;++k){
			suf[k][i]=suf[k][i+1]+a[k][i];
			ssuf[k][i]=ssuf[k][i+1]+suf[k][i];
		}
	}
	for(int i=1;i<=n;++i){
		for(int k=0;k<=1;++k){
			for(int j=0;j<i;++j){
				dp[k][i]=min(dp[k][i],dp[k^1][j]+calc(j+1,i,k));
			}
		}
	}
	cout<<"Case #"<<t<<": "<<min(dp[0][n],dp[1][n])<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int i=1;i<=T;++i){
		solve(i);
	}
	return 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
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

L-Huatuo’s Medicine

#include
#define int long long
using namespace std;

void solve(){
	int n;
	cin>>n;
	cout<<2*n-1<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	for(int i=1;i<=T;++i){
		cout<<"Case #"<<i<<": ";
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20