CF-933

当天晚上舍友在玩剧本杀，不得不说那剧情实在是太狗血了，想不通他们是怎么能玩得那么起劲的 但也不能当作这次发挥不好的借口/_ \

A题最开始没看到数据范围（D也是），B一开始就想到了思路，但调了二十多分钟，甚至因为数组开小了白白多了一次RE……D题才是最难绷的，把题看懂后自己就用的dfs的写法，直到比赛完都没调出来＞﹏＜

B

贪心，要使每个a[i]都为0，遍历到i时操作后一定有a[i-1]=0，所以a[i]-=a[i-1]*2,a[i+1]-=a[i-1]，最后看a[n-1]与a[n-1]是否为0就行

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int a[N];
void solve(){
	int n,m,k,x,ans=0,sum=0;cin>>n;
	rep(i,1,n){
		cin>>a[i];
	}
	int f=0;
	rep(i,2,n-1){
		a[i]-=a[i-1]*2;
		if(a[i]<0){
			f=1;
			break;
		}
		a[i+1]-=a[i-1];
	}
	if(a[n]!=0||a[n-1]!=0) f=1;
	if(f) cout<<"NO";
	else cout<<"YES";
	cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}

C

思路很直观：遇到map，pie与mapie都ans++，分别判断就行

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
//const int N=2e5+5;
//int a[N];
void solve(){
	int n;cin>>n;
	string s;cin>>s;
	int ans=0;
	rep(i,0,n-1){
		if(s[i]=='m'&&s[i+1]=='a'&&s[i+2]=='p'){
			if(s[i+3]=='i'&&s[i+4]=='e'){
				i+=4;	
			}
			else{
				i+=2;
			}
			ans++;
		}
		if(s[i]=='p'&&s[i+1]=='i'&&s[i+2]=='e'){
			ans++;
			i+=2;
		}
	}
	cout<<ans<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}

 

D

之前做过二分图染色的题，看到这题就往dfs的方向写了（现在想来是题面也看错了，以为只输出一种可能……）……然后赛时就在这题上吊死了……说到底还是自己技巧还有思维都还不行啊(ノへ￣、)

分析

我目前掌握的解法有bfs和dp(其实思路都一样)，bfs的话就是用set存下每个可能的玩家序号，对每个指令都遍历已存下的玩家序号进行拓展（就像迷宫，往可能的所有方向拓展），dp的话，就是对每条指令都对所有n个人中的可能的人作转移，因为要转移的状态只有可能与不可能，即1与0两种，可以用位运算或实现，注意因为是从可能的值转移过来，顺逆时针的移动公式要互换

操作

对于这种顺逆时针移动，数字范围还是[1,n]的，可以映射到[0,n-1]，也就是最开始要x–，顺时针移动就是now=(now+r)%n，逆时针是now=(now+n-r)%n，最后遍历输出set里的结果都要加一，

代码

bfs

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=1e3+5;
void solve(){
	int n,m,x;cin>>n>>m>>x;
    int r;char c;
    set<int>ans,tmp;
    x--;
    ans.insert(x);
    rep(i,1,m){
        cin>>r>>c;
        for(auto now:ans){
            if(c=='0'){
                tmp.insert((now+r)%n);
            }
            else if(c=='1'){
                tmp.insert((now+n-r)%n);
            }
            else{
                tmp.insert((now+r)%n);
                tmp.insert((now+n-r)%n);
            }
        }
        ans.clear();
        for(auto now :tmp) ans.insert(now);
        tmp.clear();
    }
    cout<<ans.size()<<endl;
    for(auto it:ans) cout <<it+1<<" ";
    cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}

dp

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
void solve(){
	int n,m,x;cin>>n>>m>>x;
	x--;
	vector<vector<int>>dp(m+1,vector<int>(n));//之前没用vector,用的普通数组，这里是用的memset，结果居然直接t了(⊙﹏⊙)
	dp[0][x]=1;
	int r;char c;
	rep(i,1,m){
		cin>>r>>c;
		if(c=='0'){
			rep(j,0,n-1){
				dp[i][j]|=dp[i-1][(j-r+n)%n];
			}
		}
		else if(c=='1'){
			rep(j,0,n-1){
				dp[i][j]|=dp[i-1][(j+r)%n];
			}
		}
		else{
			rep(j,0,n-1){
				dp[i][j]|=dp[i-1][(j+r)%n];
				dp[i][j]|=dp[i-1][(j-r+n)%n];
			}
		}
	}
	int sum=0;
    sum=count(dp[m].begin(),dp[m].end(),1);//学到了
//	rep(i,0,n-1){
//		if(dp[m][i]) sum++;
//	}
	cout<<sum<<endl;
	rep(i,0,n-1){
		if(dp[m][i]) cout<<i+1<<" ";
	}
	cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}