當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Educational Codeforces Round 56 Editorial

發布時間：2025/7/14 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了 Educational Codeforces Round 56 Editorial 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

A.Dice Rolling

題意：Mishka 有一個六面的骰子，每面分別為?

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e5+10; int a[maxn],n,t,x; int main() {scanf("%d",&t);for(int i=1;i<=t;i++){scanf("%d",&x);if(x%2==0){printf("%d\n",x/2);}else {printf("%d\n",x/2);}} } View Code

B.Letters Rearrangin

題意： $t ?組詢問，每次給你一個字符串，將其重新排列使其成為一個非回文串，如果無解則輸出?-1 ?。$

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e5+10; int a[1010],n,t,x,flag; char s[1010]; int main() {scanf("%d",&t);for(int i=1;i<=t;i++){memset(a,0,sizeof(a));flag=0;scanf("%s",&s);int l=strlen(s);for(int i=0;i<l;i++){if(a[s[i]]==0) flag++;a[s[i]]++;}if(flag==1) {printf("-1\n");continue;}for(int i=1;i<=128;i++){for(int j=1;j<=a[i];j++)printf("%c",i);}printf("\n");} } View Code

$C.Mishka and the Last Exam$

$題意：有一個長度為?$

思路：采用貪心的策略，對于任意一個bi

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e5+10; long long a[maxn],b[maxn]; int n,t,x,flag,l,r; char s[1010]; int main() {scanf("%d",&n);for(int i=1;i<=n/2;i++) scanf("%I64d",&b[i]);l=n/2;r=n/2+1;a[l]=a[r]=b[l]/2;a[r]+=b[l]%2;for(int i=n/2-1;i>=1;i--){if(b[i]-a[l]<a[r]) {a[r+1]=a[r];a[l-1]=b[i]-a[r+1];}else{a[l-1]=a[l];a[r+1]=b[i]-a[l-1];}l--;r++;}for(int i=1;i<=n;i++) printf("%I64d ",a[i]); } View Code

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int p=998244353; const int maxn=6e5+10; const int maxm=6e5+10; int x,y,z,l=0,t,n,m; int link[maxm],w[maxm],ne[maxm],first[maxn],fa[maxn]; int f[maxn]; int ans,flag,ana; long long an=1; LL quick_mod(LL a,LL b) {LL ans=1;a%=p;while(b){if(b&1) {ans=ans*a%p;b--;}b>>=1;a=a*a%p;}return ans; } void add(int x,int y) {link[++l]=y;ne[l]=first[x];first[x]=l; } int dfs(int x,int fa,bool col) {f[x]=col;ana++;if(col==0)ans++;//printf("%d %d\n",x,fa);for(int i=first[x];i;i=ne[i]){if(link[i]==fa) continue;if(f[link[i]]==-1){if (dfs(link[i],x,!col)) ;else return 0; }else {if(f[link[i]]!=(!col)) return 0;}}return 1; } int getfa(int x) {if(x==fa[x]) return x;return fa[x]=getfa(fa[x]); } int main() {scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);an=1;for(int i=1;i<=n;i++) f[i]=-1,first[i]=0,fa[i]=i;l=0;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);int fx=getfa(x),fy=getfa(y);fa[fx]=fy;add(x,y);add(y,x);}flag=1;for(int i=1;i<=n;i++){ans=0;ana=0;if(fa[i]==i){if(dfs(i,0,0)){//printf("%d %d %d\n",i,ana,ans);an=an*(quick_mod(2,ans)+quick_mod(2,ana-ans))%p;}else {flag=0;break;}}}if(!flag) printf("0\n");else printf("%I64d\n",an);} } View Code

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,m,ta[N],tb[N],pa[N],pb[N],ans[N],tot,f[N],cnt; struct node{bool fx;int x,y,k,id,tim;node(int f=0,int x=0,int y=0,int k=0,int i=0,int t=0):fx(f),x(x),y(y),k(k),id(i),tim(t) {}bool operator< (const node &b) const{return x<b.x||(x==b.x&&tim<b.tim);} }a[(N<<2)+N],b[(N<<2)+N]; void add(int x,int k){for(;x<=n;x+=(x&-x))f[x]+=k;} int query(int x){int ret=0;for(;x;x-=(x&-x))ret+=f[x];return ret;} void solve(int l,int r) {if(l>=r) return;int mid=(l+r)>>1,p0=l,p1=mid+1;for(int i=l;i<=r;i++)if(!a[i].fx&&a[i].tim<=mid) add(a[i].y,a[i].k);else if(a[i].fx&&a[i].tim>mid) ans[a[i].id]+=a[i].k*query(a[i].y);for(int i=l;i<=r;i++)if(!a[i].fx&&a[i].tim<=mid) add(a[i].y,-a[i].k);for(int i=l;i<=r;i++)if(a[i].tim<=mid) b[p0++]=a[i];else b[p1++]=a[i];for(int i=l;i<=r;i++) a[i]=b[i];solve(l,mid);solve(mid+1,r); } int main() {scanf("%d",&n);scanf("%d",&m);for(int i=1;i<=n;i++) scanf("%d",&ta[i]),pa[ta[i]]=i;for(int i=1;i<=n;i++) scanf("%d",&tb[i]),pb[tb[i]]=i;for(int i=1;i<=n;i++)a[++cnt]=node(0,pa[i],pb[i],1,0,cnt);for(int i=1,op,x1,y1,x2,y2,w1,w2;i<=m;i++){scanf("%d",&op);if(op==1){tot++;scanf("%d",&x1);scanf("%d",&x2);scanf("%d",&y1);scanf("%d",&y2);x1--;y1--;a[++cnt]=node(1,x2,y2,1,tot,cnt);a[++cnt]=node(1,x1,y2,-1,tot,cnt);a[++cnt]=node(1,x2,y1,-1,tot,cnt);a[++cnt]=node(1,x1,y1,1,tot,cnt);}else{scanf("%d",&w1);scanf("%d",&w2);y1=w1;x1=pa[tb[w1]];y2=w2;x2=pa[tb[w2]];swap(tb[w1],tb[w2]);a[++cnt]=node(0,x2,y2,-1,0,cnt);a[++cnt]=node(0,x1,y1,-1,0,cnt);a[++cnt]=node(0,x2,y1,1,0,cnt);a[++cnt]=node(0,x1,y2,1,0,cnt);}} sort(a+1,a+1+cnt);solve(1,cnt);for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);return 0; } View Code

#include<bits/stdc++.h> using namespace std; #define RI register int int read() {int q=0;char ch=' ';while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();return q; } const int N=200005; int n,m,qcnt; int a[N],X[N],T[N],ans[N],s[N]; struct node{int x,Y1,Y2,id;}; vector<node> tr[N<<2];void insq(int x,int s,int t,int i,node k) {//將詢問放在時間線段樹上tr[i].push_back(k); if(s==t) return;int mid=(s+t)>>1;if(x<=mid) insq(x,s,mid,i<<1,k);else insq(x,mid+1,t,(i<<1)|1,k); } void insp(int l,int r,int s,int t,int i,node k) {//將點放在時間線段樹上if(l<=s&&t<=r) {tr[i].push_back(k);return;}int mid=(s+t)>>1;if(l<=mid) insp(l,r,s,mid,i<<1,k);if(mid+1<=r) insp(l,r,mid+1,t,(i<<1)|1,k); }bool cmp(node A,node B) {return A.x==B.x?A.id==0:A.x<B.x;} int lowbit(int x) {return x&(-x);} void add(int x,int v) {while(x<=n) s[x]+=v,x+=lowbit(x);} int query(int x) {int re=0; while(x) re+=s[x],x-=lowbit(x); return re;} void work(int s,int t,int i) {sort(tr[i].begin(),tr[i].end(),cmp);//掃描線int sz=tr[i].size();for(RI j=0;j<sz;++j) {if(!tr[i][j].id) add(tr[i][j].Y1,1);else {int kl=query(tr[i][j].Y2)-query(tr[i][j].Y1-1);if(tr[i][j].id<0) ans[-tr[i][j].id]-=kl;else ans[tr[i][j].id]+=kl;}}for(RI j=0;j<sz;++j) if(!tr[i][j].id) add(tr[i][j].Y1,-1);if(s==t) return;int mid=(s+t)>>1;work(s,mid,i<<1),work(mid+1,t,(i<<1)|1); }int main() {int op,X1,Y1,X2,Y2;n=read(),m=read();for(RI i=1;i<=n;++i) a[read()]=i;for(RI i=1;i<=n;++i) X[i]=a[read()],T[i]=0;for(RI i=1;i<=m;++i) {op=read();if(op==1) {X1=read(),X2=read(),Y1=read(),Y2=read(),++qcnt;insq(i,0,m,1,(node){X1-1,Y1,Y2,-qcnt});insq(i,0,m,1,(node){X2,Y1,Y2,qcnt});}else {X1=read(),X2=read();insp(T[X1],i-1,0,m,1,(node){X[X1],X1,0,0});insp(T[X2],i-1,0,m,1,(node){X[X2],X2,0,0});swap(X[X1],X[X2]),T[X1]=T[X2]=i;}}for(RI i=1;i<=n;++i) insp(T[i],m,0,m,1,(node){X[i],i,0,0});work(0,m,1);for(RI i=1;i<=qcnt;++i) printf("%d\n",ans[i]);return 0; } View Code

F.?Vasya and Array

題意：給你一個長度為n的序列，一個正整數K，和長度len，序列中的數都是1-k或者為-1，-1表示可以填任何數。讓你在-1的地方填數，使得沒有長度？len的相等數字。

思路：DP，DP[i][j]表示填到第i為的數字為j的方案數,S[i]為DP[i][j](1<=j<=k)注意轉移

#include <bits/stdc++.h> #define md 998244353 #define maxn 100001 #define max(a,b) (a>b?a:b) #define maxk 101 int n,k,len,a[maxn]; int f[maxn][maxk],s[maxn],cnt[maxn][maxk]; void inc(int &a,int b){a=((a+b>=md)?a+b-md:a+b);} int main(){scanf("%d%d%d",&n,&k,&len);for (register int i=1;i<=n;++i)scanf("%d",&a[i]);for (register int i=1;i<=n;++i)for (register int j=1;j<=k;++j)inc(cnt[i][j],cnt[i-1][j]+(a[i]==j||a[i]==-1));for (register int i=1;i<=n;++i){for (register int j=1;j<=k;++j){if (!(a[i]==j||a[i]==-1)) continue;int add=1;if (i>1) add=s[i-1];inc(f[i][j],add);bool ok=i>=len;int l=max(1,i-len+1);ok&=(cnt[i][j]-cnt[l-1][j]==len);if (!ok) continue;if (i==len) {inc(f[i][j],md-1);continue;}int sum=f[i-len][j];inc(sum,md-s[i-len]);inc(f[i][j],sum);}for (register int j=1;j<=k;++j)inc(s[i],f[i][j]);}printf("%d\n",s[n]); } View Code

G.Multidimensional Queries

題意：給你?

#include <bits/stdc++.h> #define Fast_cin ios::sync_with_stdio(false), cin.tie(); #define rep(i, a, b) for(register int i = a; i <= b; i++) #define per(i, a, b) for(register int i = a; i >= b; i--) #define DEBUG(x) cerr << "DEBUG" << x << " >>> " << endl; using namespace std;typedef unsigned long long ull; typedef long long ll;template <typename _T> inline void read(_T &f) {f = 0; _T fu = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); }while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }f *= fu; }template <typename T> void print(T x) {if(x < 0) putchar('-'), x = -x;if(x < 10) putchar(x + 48);else print(x / 10), putchar(x % 10 + 48); }template <typename T> void print(T x, char t) {print(x); putchar(t); }const int N = 2e5 + 5;struct ele { int f[32]; };struct Node {int l, r; ele val; }p[N << 2];int t[N][5]; int n, m, k;ele merge(ele a, ele b) {for(register int i = 0; i < (1 << k); i++) a.f[i] = max(a.f[i], b.f[i]);return a; }void build(int u, int l, int r) {p[u].l = l; p[u].r = r;if(l == r) {for(register int i = 0; i < (1 << k); i++) {p[u].val.f[i] = 0;for(register int j = 0; j < k; j++) {if(i & (1 << j)) p[u].val.f[i] += t[l][j];else p[u].val.f[i] -= t[l][j];}}return;}int mid = (l + r) >> 1;build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);p[u].val = merge(p[u << 1].val, p[u << 1 | 1].val); }void change(int u, int l) {if(p[u].l == p[u].r) {for(register int i = 0; i < (1 << k); i++) {p[u].val.f[i] = 0;for(register int j = 0; j < k; j++) {if(i & (1 << j)) p[u].val.f[i] += t[l][j];else p[u].val.f[i] -= t[l][j];}}return;}int mid = (p[u].l + p[u].r) >> 1;if(mid >= l) change(u << 1, l); else change(u << 1 | 1, l);p[u].val = merge(p[u << 1].val, p[u << 1 | 1].val); }ele query(int u, int l, int r) {if(p[u].l >= l && p[u].r <= r) return p[u].val;int mid = (p[u].l + p[u].r) >> 1;if(mid >= l && mid + 1 <= r) return merge(query(u << 1, l, r), query(u << 1 | 1, l, r));else if(mid >= l) return query(u << 1, l, r); return query(u << 1 | 1, l, r); }int main() {read(n); read(k);for(register int i = 1; i <= n; i++) {for(register int j = 0; j < k; j++) {read(t[i][j]);}}build(1, 1, n); read(m);while(m--) {int opt; read(opt);if(opt == 1) {int i; read(i); // cout << i << " " << k << endl;for(register int j = 0; j < k; j++) read(t[i][j]);change(1, i);}if(opt == 2) {int l, r; read(l); read(r);ele res = query(1, l, r); int ans = 0;for(register int i = 0; i < (1 << (k - 1)); i++) ans = max(ans, res.f[i] + res.f[(1 << k) - 1 - i]);print(ans, '\n');}}return 0; } View Code

轉載于:https://www.cnblogs.com/The-Pines-of-Star/p/10340954.html

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 56 Editorial的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。