「CF623X」AIM Tech Round (Div. 1)
A. Graph and String
题意
n个点，每个点有a,b,c其中一种颜色，若两个点颜色的字母相邻则它们之间连边。
给出图的连边情况，求一种可行的染色方案。
题解
如果有一个点和其它点都有连边，将其标号b。
然后选择一个未被标号的点，标号为a，二分图染色。
最后验证一下即可。
|
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 67 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #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; bool e[505][505]; int v[505]; void solve(int x,int y) { for(int i=1;i<=n;i++) if(i!=x&&i!=y) { if(e[i][x])v[i]=1; if(e[i][y])v[i]=3; if(e[i][x]&&e[i][y])v[i]=2; } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); e[u][v]=e[v][u]=1; } bool flag=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!e[i][j]) { v[i]=1;v[j]=3; solve(i,j); flag=1; break; } if(!flag)for(int i=1;i<=n;i++)v[i]=1; for(int i=1;i<=n;i++)if(!v[i]){puts("No");return 0;} for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(abs(v[i]-v[j])<=1&&!e[i][j]){puts("No");return 0;} if(abs(v[i]-v[j])==2&&e[i][j]){puts("No");return 0;} } puts("Yes"); for(int i=1;i<=n;i++) printf("%c",'a'+v[i]-1); printf("\n"); return 0; |
B. Array GCD
题意
给定长为n的数列和两个操作，每个操作用一次
1.移除数列的一个子串，代价是长度*a
2.对于一些数字+1或者-1，每个数字代价为b
求使得数列的gcd大于1的最小代价
题解
由于不能删掉所有的数，那么至少会剩下第一个或最后一个
这两个可能会被修改，枚举2 * 3 = 6种情况，分解质因数后扫一遍数列，取最优值
|
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 67 68 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #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 mn; int n; ll a,b; int v[1000005]; ll c[1000005],f[1000005]; void cal(int x) { ll l=1,r=n,g=0; for(int i=1;i<=n;i++) { if(v[i]%x==1||v[i]%x==x-1)c[i]=b; else if(v[i]%x==0)c[i]=0; else c[i]=mn; } for(int i=1;i<=n;i++) f[i]=min(f[i-1]+c[i],mn); for(int i=1;i<=n;i++) f[i]=min(f[i-1],f[i]-a*i); for(int i=n;i;i--) { mn=min(mn,f[i]+g+a*i); g=min(g+c[i],mn); } } void solve(int t) { for(int i=2;i<=100000;i++) if(t%i==0) { cal(i); while(t%i==0)t/=i; } if(t!=1)cal(t); } int main() { n=read();a=read();b=read(); mn=(n-1)*a; for(int i=1;i<=n;i++) v[i]=read(); for(int i=-1;i<=1;i++) solve(i+v[1]),solve(i+v[n]); cout<<mn<<endl; return 0; } |
Subscribe