AtCoder Beginner Contest 250 (ABC250) 题解 （A-Ex）
～～～新鲜出炉～～～
统一链接：https://atcoder.jp/contests/abc250/tasks
这次比较水啊（特别是C），但是说D题的数学题不那么简单（但看了这个题确实不难）
下面开始题解：
A题：
题意：给定格子长宽和一个格子的行列，求那个格子的相邻格子的数量。
这个题还是比较友好的，把所有情况都告诉你了，除了只有1行或者只有1列的情况比较难想到，下面代码：
//AT250A 22-05-08#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);int h,w,r,c,s=4;cin>>h>>w>>r>>c;if (r==1 || r==h) s--;if (c==1 || c==w) s--;if (h==1 || w==1) s--;if (h==1 && r==1 && c==1 && w==1) s=0;cout<<s<<endl;return 0;}B题：
题意：按要求输出：给定区块长宽，间隔输出 # 和 . 。
#的情况就是长和宽的绝对值差为奇数，.就是差为偶数，看代码：
//AT250B 22-05-08#include using namespace std;char c[105][105];int main() {ios::sync_with_stdio(0);cin.tie(0);int n,a,b;cin>>n>>a>>b;for (int p=1;p<=n;p++){for (int q=1;q<=n;q++)if (abs(q-p)%2==0){for (int i=1;i<=a;i++)for (int j=1;j<=b;j++)c[p*a-a+i][q*b-b+j]='.';}else{for (int i=1;i<=a;i++)for (int j=1;j<=b;j++)c[p*a-a+i][q*b-b+j]='#';}}for (int i=1;i<=a*n;i++){for (int j=1;j<=b*n;j++)cout<<c[i][j];cout<<endl;}return 0;}C题
题意：给定长度为 N 的数组，进行操作：
共有 Q 个询问：
给定一个数，查找这个数，然后交换它与右边的元素，如果是最右边，就交换第 N-1 个元素
求出操作完的数组。
分析：硬查找肯定不行 4*10^10 绝对出事，需要每次记录位置，然后模拟就行了。
//AT250C 22-05-08#includeusing namespace std;int p[200005],rev[200005],a[200005];int main(){ios::sync_with_stdio(0);cin.tie(0);int n,q;cin>>n>>q;//p 指第 i 个球放的位置for (int i=1;i>x;if (p[x]==n){int tmp=p[x];swap(p[x],p[a[tmp-1]]);swap(a[tmp],a[tmp-1]);}else{int tmp=p[x];swap(p[x],p[a[tmp+1]]);swap(a[tmp],a[tmp+1]);}}for (int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;}===============稍后更新================
Upd: 22-05-10
大家最需要的D题题解来了～～～
D题：
题意：有一种数：当两个素数 p, q（p<q）满足 时，满足条件（N为给定数）。
求这种数有多少个。
分析：主要思路：枚举+素数判断+范围判断
先把N开三次方，然后就会得到q的上限。
接着开始枚举q，
如果是素数（*），则接着枚举p，然后判断是否大于N。
*：注意这里要用素数筛法，不然大数据评测，可能会TLE。
不会素数筛法，请参考：https://blog.csdn.net/zeekliu/article/details/124091682
代码：
//AT250D 22-05-08#include using namespace std;long long n,t;bool b[1000010];int p[200010];bool prime(int n){if (n==1) return 0;else for (int i=3;i>n;t=pow(n,1.0/3);memset(b,0,sizeof(b));for (int i=4;i<=t;i+=2)b[i]=1;for (int i=3;i<=t;i+=2){if (prime(i)){for (int j=2;j<=t/i;j++) b[j*i]=1;}}int m=0;for (int i=2;i<=t;i++) if (b[i]==0){m++;p[m]=i;}long long s=0;for (int i=1;i<=m;i++){for (int j=1;jn) break;s++;//cout<<y<<" ";}}cout<<s<<endl;return 0;}下面E F G Ex (H) 较难。
E题：
#include using namespace std;typedef long long ll;templatebool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }templatebool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=2000005;const ll INF=1LL<>N; map MA; set SE; vector A(N),B(N); ll rui=0; for(int i=0;i>x; if(MA[x]){ if(!SE.count(x)){ rui^=MA[x]; SE.insert(x); } }else{ ll y=rng()%INF; MA[x]=y; rui^=MA[x]; SE.insert(x); } A[i]=rui; } rui=0; SE.clear(); for(int i=0;i>x; if(MA[x]){ if(!SE.count(x)){ rui^=MA[x]; SE.insert(x); } }else{ ll y=rng()%INF; MA[x]=y; rui^=MA[x]; SE.insert(x); } B[i]=rui; } int Q;cin>>Q; while(Q--){ int a,b;cin>>a>>b;a--;b--; if(A[a]==B[b]){ cout<<"Yes\n"; }else{ cout<<"No\n"; } }}F题：
#include using namespace std;struct point{ long long x, y; point(){ } point(long long x, long long y): x(x), y(y){ } point operator -(point P){ return point(x - P.x, y - P.y); }};long long cross(point P, point Q){ return P.x * Q.y - P.y * Q.x;}long long area(point A, point B, point C){ return abs(cross(B - A, C - A));}int main(){ int N; cin >> N; vector P(N); for (int i = 0; i > P[i].x >> P[i].y; } long long a = 0; for (int i = 0; i < N - 1; i++){ a += cross(P[i], P[i + 1]); } a += cross(P[N - 1], P[0]); int R = 0; long long b = 0; long long ans = a; for (int L = 0; L < N; L++){ while (b <= a){ int R2 = (R + 1) % N; long long add = area(P[L], P[R], P[R2]); b += add * 4; ans = min(ans, abs(a - b)); R = R2; } int L2 = (L + 1) % N; long long sub = area(P[L], P[L2], P[R]); b -= sub * 4; ans = min(ans, abs(a - b)); } cout << ans << endl;}G题：
#include using namespace std;typedef long long ll;templatebool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }templatebool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=2005;const ll INF=1LL<>N; multiset MS; ll ans=0; for(int i=0;i>x; if(i==0){ MS.insert(x); }else{ if(x<=*MS.begin()) MS.insert(x); else{ MS.erase(MS.begin()); MS.insert(x); MS.insert(x); } } ans-=x; } for(ll a:MS) ans+=a; chmax(ans,0LL); cout<<ans<<endl;}H题：
#include using namespace std;typedef long long ll;templatebool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }templatebool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=200005;const ll INF=1LL<<61;struct UF{ int n; vector par,size,edge; void init(int n_){ n=n_; par.assign(n,-1); size.assign(n,1); edge.assign(n,0); for(int i=0;i<n;i++){ par[i]=i; } } int root(int a){ if(par[a]==a) return a; else return par[a]=root(par[a]); } void unite(int a,int b){ edge[root(a)]++; if(root(a)!=root(b)){ size[root(a)]+=size[root(b)]; edge[root(a)]+=edge[root(b)]; par[root(b)]=root(a); } } bool check(int a,int b){ return root(a)==root(b); }};int N,M,K;vector<pair> G[MAX];ll dis[MAX];void dijkstra(){ priority_queue<pair,vector<pair>,greater<pair>> PQ; for(int i=0;i<N;i++) dis[i]=INF; for(int i=0;i<K;i++){ dis[i]=0; PQ.push(mp(0LL,i)); } while(!PQ.empty()){ ll a=PQ.top().first; int b=PQ.top().second; PQ.pop(); if(dis[b]<a) continue; for(int i=0;idis[b]+d){ dis[c]=dis[b]+d; PQ.push(make_pair(dis[c],c)); } } } return;}int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); cin>>N>>M>>K; for(int i=0;i>a>>b>>c; a--;b--; G[a].push_back(mp(b,c)); G[b].push_back(mp(a,c)); } dijkstra(); vector<pair<pair,ll>> E; for(int i=0;i<N;i++){ for(auto to:G[i]){ if(i<to.fi) E.push_back(mp(mp(i,to.fi),dis[i]+dis[to.fi]+to.se)); } } sort(all(E),[](auto a,auto b){ return a.se>Q; int i=0; while(Q--){ int a,b;ll c;cin>>a>>b>>c;a--;b--; while(i<si(E)&&E[i].se<=c){ uf.unite(E[i].fi.fi,E[i].fi.se); i++; } if(uf.check(a,b)){ cout<<"Yes\n"; }else{ cout<<"No\n"; } }}
