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;
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。