Educational Codeforces Round 56 Editorial
生活随笔
收集整理的這篇文章主要介紹了
Educational Codeforces Round 56 Editorial
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
A.Dice Rolling
題意：Mishka 有一個六面的骰子，每面分別為?2?~?7，而且 Mishka 是歐皇，可以控制自己每次擲到的數字。Mishka 現在想擲若干次骰子，使得擲到的點數總和為?x，請求出任意一種擲骰子的方案，并輸出擲骰子的次數。由于 Mishka 很好奇不同數字的方案，所以有?t?組詢問。
?
#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 CodeB.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 CodeC.Mishka and the Last Exam
題意：有一個長度為?n（n?為偶數）的數列?a1..n?，ai<=ai+1?，bi=ai+an-i+1, 現在告訴你?n?和?b1..n/2??，求a1..n??。
思路：采用貪心的策略，對于任意一個bi，讓a n-i+1盡可能大，ai盡能小，所以從中間開始貪心。（注意long long）
?
#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 CodeD.Beautiful Graph
題意：給你一個?n?個點?m?條邊的無向圖。你需要給每個點一個點權，使得每條邊連接的兩個點點權奇偶不同。點權的值域為?{1,2,3}。請求出方案數對?998244353?取模的結果。圖中沒有重邊或自環。
思路：要做一次?bfsbfs?染色并判斷是否能完成染色即可bfs染色，加個快速冪即可
?
#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?
E.Intersection of Permutations
題意：給你長度為n的兩個序列，有m個詢問，1 la ra lb rb 表示查詢a數組[la,ra]區間內和b數組[lb,rb]區間內相同的數的個數，2?x?y，交換?b數組?的第?x?位與第?y?位
思路1：用?pa[i]表示?i這個數在第一個排列中出現的位置，pb[i]表示?i這個數在第二個排列中出現的位置，那么容易發現問題變成了二維數點問題，cdq?分治離線統計答案即可
?
#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思路2：時間線段樹+掃描線
上一棵時間線段樹。將一個點覆蓋在它出現的時間區間內，一個詢問則在從單獨代表這個詢問的時間的線段樹節點到線段樹的根的路徑上都放一個，遍歷線段樹的時候，
對于每個節點上放的詢問們和點們，都做一遍掃描線。
?
#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
題意：給你?n?個?k?維的點?，求區間內兩個點曼哈頓距離的最大值。
思路：習慣性的把曼哈頓距離的絕對值拆出來，用二進制表示31?的二進制表示是?11111，表示?5維的一個點的坐標加入的正負情況都為正（即?x[1] - y[1] + x[2] - y[2] + x[3] - y[3] + x[4] - y[4] + x[5] - y[5]?
用線段樹維護
?
?
#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的全部內容，希望文章能夠幫你解決所遇到的問題。
