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;
}