「CF339X」Codeforces Round #197 (Div. 2)
A. Helpful Maths
排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1e16 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; string a; int b[1005]; int main() { cin>>a; int t=0; for(int i=0;i<a.length();i++) if(a[i]=='+')b[++n]=t,t=0; else t=t*10+a[i]-'0'; b[++n]=t; sort(b+1,b+n+1); printf("%d",b[1]); for(int i=2;i<=n;i++)printf("+%d",b[i]); return 0; } |
B. Xenia and Ringroad
题意即题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int n,m; int a[100005]; int main() { n=read();m=read(); for(int i=1;i<=m;i++)a[i]=read(); a[0]=1; for(int i=1;i<=m;i++) if(a[i]>=a[i-1])ans+=a[i]-a[i-1]; else ans+=n+a[i]-a[i-1]; cout<<ans<<endl; return 0; } |
C. Xenia and Weights
搜索可过
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,a[1005]; char ch[15]; int dfs(int k,int d) { if(k>n)return 1; for(int i=d+1;i<=10;i++) if(a[k-1]!=i&&ch[i]=='1') { a[k]=i; if(dfs(k+1,i-d))return 1; } return 0; } int main() { scanf("%s",ch+1); n=read(); if(dfs(1,0)) { puts("YES"); for(int i=1;i<=n;i++) printf("%d ",a[i]); puts(""); } else puts("NO"); return 0; } |
D. Xenia and Bit Operations
线段树模拟
每次询问可以自底向上修改
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[20][200005]; void update(int n,int p,int f) { if(n==0)return; int t=p; if(p&1)t++; else t--; if(f==1) a[n-1][(p+1)/2]=a[n][p]|a[n][t]; else a[n-1][(p+1)/2]=a[n][p]^a[n][t]; update(n-1,(p+1)/2,f^1); } int main() { n=read();m=read(); for(int i=1;i<=(1<<n);i++)a[n][i]=read(); for(int i=1;i<=(1<<n);i++)update(n,i,1); for(int i=1;i<=m;i++) { int p=read(),v=read(); a[n][p]=v; update(n,p,1); printf("%d\n",a[0][1]); } return 0; } |
E. Three Swaps
由于只有三次交换,所以数列最多被分成七段
找到所有断点爆搜
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n,top; int a[1005],L[5],R[5]; bool check() { for(int i=1;i<=n;i++) if(a[i]!=i)return 0; return 1; } void rever(int l,int r) { if(l>r)swap(l,r); L[top]=l;R[top]=r; for(int i=0;i<(r-l+1)/2;i++) swap(a[l+i],a[r-i]); } void dfs(int k) { if(flag)return; if(check()) { flag=1; printf("%d\n",top); for(int i=top;i;i--) printf("%d %d\n",L[i],R[i]); return; } if(k==0)return; for(int i=1;i<=n;i++) if(a[i]!=i&&(abs(a[i]-a[i-1])!=1||abs(a[i]-a[i+1])!=1)) for(int j=i+1;j<=n;j++) if(a[j]!=j&&(abs(a[j]-a[j-1])!=1||abs(a[j]-a[j+1])!=1)) { top++;rever(i,j); dfs(k-1); rever(L[top],R[top]);top--; } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); a[0]=a[n+1]=-1; dfs(3); return 0; } |
黄学长又在屠题,可怕!