AtCoder Beginner Contest 298

A题意：给一个字符串，如果里面含有字符o并且不含字符x，输出“Yes”，否则输出“No”。

code：

#include<bits/stdc++.h>using namespace std;int main(){int n;cin>>n;string s;cin>>s;bool flag1 = 0;bool flag2 = 0;for(int i=0;i<s.size();i++){if(s[i] == 'o') flag1 = 1;if(s[i] == 'x') flag2 = 1;}if(flag1 && !flag2) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
} 

B题意：给两个N * N的矩阵A,B。对矩阵A能进行以下操作，对A中所有的(i,j)坐标，能将其取代为(N+1-j,i)的值。该操作能使用无数次，问是否能使得矩阵A进行过若干次操作后，A矩阵里面所有位置为1的位置在B矩阵中同样为一。如果可以就输出Yes，否则就输出No。

思路：A矩阵应该是执行若干次操作后会变回来原来的矩阵。但这里我不想深究了。就让A执行操作1000次，同时判断在这些操作中A中位置为1的地方在B中是否也为1.

#include<bits/stdc++.h>using namespace std;
#define maxn 104
int a[maxn][maxn];
int b[maxn][maxn];
int c[maxn][maxn];//记录中间过程 
int n;bool check2(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j] == 1){if(b[i][j]!=1) return false;}}}return true;
}
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];c[i][j]=a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>b[i][j];}}
//	A执行变型操作能不能变成Bbool flag = 0;int k =1000;while(k--){if(check2()){flag =1;break; } for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j] = c[n+1-j][i];}}for(int i=1;i<=n;i++){//记录新数组 for(int j=1;j<=n;j++){c[i][j] = a[i][j];}}}if(flag) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

C - Cards Query Problem

题意: 这里就是有N个箱子，无数张卡片。执行Q次操作，这里一共有三种操作。

• 第一就是把写上数字i的卡片放箱子j中
• 第二就是打印箱子i中所有的卡片上的数字，升序，不去重
• 第三就是打印所有含有数字j的箱子的序号，升序，去重

思路：
这里很显然用multiset 和 set是最契合的，因为其不仅仅能自动排序并且可以实现不去重或者去重。

#include<bits/stdc++.h>using namespace std;
int x,y;//x表示卡片上的数字，y表示箱子 
int n;	
int q;  
int nn;
//n个空箱子，无数张卡片，
//三种操作，1. i->j  2. 写出i箱子里所有卡片上的数字 3.写出所有含有数字i卡片的箱子 
#define maxn 200001multiset<int> box[maxn];
set<int> num[maxn];int main(){cin>>n;cin>>q;while(q--){cin>>nn;if(nn == 1){cin>>x>>y;//写一个数字x放入y箱子 box[y].insert(x); num[x].insert(y);} else if(nn == 2){cin>>y;//写出箱子y中所有卡片的数字 for(auto i:box[y]) cout<<i<<" "; cout<<endl;}else{cin>>x;//出所有含有数字i卡片的箱子  for(auto j:num[x]) cout<<j<<" ";cout<<endl;} } return 0;
} 

D - Writing a Numeral
题意：这里意思是有一个字符串S，可以执行Q次操作。
操作有三种类型

• 在字符串后面添加一个数字x
• 删除字符串首个字符
• 打印字符串变为整数后对998244353取余的数

思路：因为数据范围比较大，所以我们需要注意时间效率。
我们可以用数组来模拟字符串，添加元素相当于往数组里面添加元素，删除相当于把指针后移即可。在这个过程中，计算now即为3操作当前的值。

详细见代码，就是维护一个数组更新now值就行了，操作二中因为我们删除了首字符，相当于减去了 首字符数字 * 对应的位数对应的十进制的值。

#include<bits/stdc++.h>
#define mod 998244353
#define maxn 600001
using namespace std;
typedef long long ll;ll p[maxn];
ll a[maxn];
int c;
int l;
int q;
int nn;int main(){p[0] = 1;int n = 1;ll now = 1;a[1]=1;l = 1;cin>>q;for(int i=1;i<=q;i++){//所有的操作都是添加的最大值 1 10 100 p[i] = p[i-1] * 10 % mod;}while(q--){cin>>nn;if(nn==1){cin>>c;a[++n] = c;now=(now*10+a[n])%mod;//表示现在那个数字 }else if(nn == 2){now=(now-p[n-l]*a[l]%mod+mod)%mod;//减去前面删掉的数 l++;}else{cout<<now<<endl;	}}return 0;
}

分享一下大佬duque做法

#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using ll=long long;
using vll=vector<long long>;
using vvll=vector<vector<long long>>;
#define rep(i,j,n) for(int i=j;i<n;i++)
#define MOD 1000000007
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;int main()
{int Q;cin >> Q;int t,x;deque<int> S; mint N=1;S.push_back(1);rep(i,0,Q){cin >> t;if(t==1){cin >> x;S.push_back(x);N=N*10+x;}if(t==2){N=N-S.front()*mint(10).pow(S.size()-1);S.pop_front();}if(t==3){cout << N.val() << endl;}}return 0;
}