544A. Set of Strings
You are given a string q . A sequence of k strings s 1, s 2, ..., s k is called beautiful, if the concatenation of these strings is string q (formally, s 1 + s 2 + ... + s k = q ) and the first characters of these strings are distinct.
Find any beautiful sequence of strings or determine that the beautiful sequence doesn't exist.
每个在之前没有出现过的字母作一个标记,作为每个字符串的开头
1 var i,k,j:longint; 2 vis:array['a'..'z']of boolean; 3 v:array[-1..110]of boolean; 4 s:ansistring; 5 6 begin 7 readln(k); 8 readln(s); 9 fillchar(vis,sizeof(vis),true); 10 fillchar(v,sizeof(v),true); 11 for i:=1 to length(s) do if vis[s[i]] then 12 begin 13 vis[s[i]]:=false;v[i]:=false;dec(k); 14 if k=0 then break; 15 end; 16 if k>0 then writeln('NO') else 17 begin 18 writeln('YES'); 19 i:=1; 20 while i<=length(s) do 21 begin 22 write(s[i]); 23 j:=i+1; 24 while (j<=length(s))and(v[j]) do 25 begin 26 write(s[j]); 27 inc(j); 28 end; 29 writeln; 30 i:=j; 31 end; 32 end; 33 end.
544B. Sea and Islands
A map of some object is a rectangular field consisting of n rows and n columns. Each cell is initially occupied by the sea but you can cover some some cells of the map with sand so that exactly k islands appear on the map. We will call a set of sand cells to be island if it is possible to get from each of them to each of them by moving only through sand cells and by moving from a cell only to a side-adjacent cell. The cells are called to be side-adjacent if they share a vertical or horizontal side. It is easy to see that islands do not share cells (otherwise they together form a bigger island).
Find a way to cover some cells with sand so that exactly k islands appear on the n × n map, or determine that no such way exists.
1 var i,j,n,k:longint; 2 begin 3 readln(n,k); 4 if k>(n*n+1) >> 1 then writeln('NO') else 5 begin 6 writeln('YES'); 7 for i:=1 to n do 8 begin 9 for j:=1 to n do if ((i+j) and 1=0)and(k>0) then 10 begin 11 write('L');dec(k); 12 end else write('S'); 13 writeln; 14 end; 15 end; 16 end.
543A. Writing Code
Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i -th of them makes exactly a i bugs in every line of code that he writes.
Let's call a sequence of non-negative integers v 1, v 2, ..., v n a plan, if v 1 + v 2 + ... + v n = m . The programmers follow the plan like that: in the beginning the first programmer writes the first v 1 lines of the given task, then the second programmer writes v 2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let's call a plan good, if all the written lines of the task contain at most b bugs in total.
Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod .
一直觉得要枚举一个数量所以n^4...甚至想要去写二进制背包这种两年没写过的东西...
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 int a[510],f[510][510]; 5 int main(){ 6 int n,m,b,tt; 7 scanf("%d%d%d%d",&n,&m,&b,&tt); 8 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 9 f[0][0] = 1; 10 for (int i=1;i<=n;i++) 11 for (int j=1;j<=m;j++) 12 for (int k=a[i];k<=b;k++) f[j][k]=(f[j][k]+f[j-1][k-a[i]])%tt; 13 int ans=0; 14 for (int i=0;i<=b;i++) ans=(ans+f[m][i])%tt; 15 printf("%d/n",ans); 16 return 0; 17 }
543B. Destroying Roads
In some country there are exactly n cities and m bidirectional roads connecting the cities. Cities are numbered with integers from 1 to n . If cities a and b are connected by a road, then in an hour you can go along this road either from city a to city b , or from city b to city a . The road network is such that from any city you can get to any other one by moving along the roads.
You want to destroy the largest possible number of roads in the country so that the remaining roads would allow you to get from city s 1to city t 1 in at most l 1 hours and get from city s 2 to city t 2 in at most l 2 hours.
Determine what maximum number of roads you need to destroy in order to meet the condition of your plan. If it is impossible to reach the desired result, print -1.
然而还有一种方法,就是让两条路径重合,可以证明得到,重合的部分一定是连续的一段
1 const maxn = 3010;maxm=200010;INF=100000007; 2 var fa,next:array[-1..maxm]of longint; 3 link,opt:array[-1..maxn]of longint; 4 vis:array[-1..maxn]of boolean; 5 dis:array[-1..maxn,-1..maxn]of longint; 6 ans,s1,t1,h1,s2,t2,h2,n,m,e,i,x,y,j:longint; 7 8 procedure add(x,y:longint); 9 begin 10 inc(e);fa[e]:=y;next[e]:=link[x];link[x]:=e; 11 inc(e);fa[e]:=x;next[e]:=link[y];link[y]:=e; 12 end; 13 14 function min(a,b:longint):longint; 15 begin 16 if a<b then exit(a) else exit(b); 17 end; 18 19 function max(a,b:longint):longint; 20 begin 21 if a>b then exit(a) else exit(b); 22 end; 23 24 procedure bfs(s:longint); 25 var head,tail,x,j,i:longint; 26 begin 27 for i:=1 to n do dis[i,s]:=INF; 28 fillchar(vis,sizeof(vis),true); 29 head:=0;tail:=1;dis[s,s]:=0;vis[s]:=false;opt[1]:=s; 30 while head<>tail do 31 begin 32 inc(head); 33 x:=opt[head];j:=link[x]; 34 while j<>0 do 35 begin 36 if vis[fa[j]] then 37 begin 38 vis[fa[j]]:=false; 39 dis[fa[j],s]:=dis[x,s]+1; 40 inc(tail);opt[tail]:=fa[j]; 41 end; 42 j:=next[j]; 43 end; 44 end; 45 end; 46 47 begin 48 readln(n,m); 49 e:=0; 50 for i:=1 to m do 51 begin 52 readln(x,y);add(x,y); 53 end; 54 for i:=1 to n do bfs(i); 55 readln(s1,t1,h1);readln(s2,t2,h2); 56 ans:=-1; 57 if (dis[s1,t1]<=h1)and(dis[s2,t2]<=h2) then ans:=max(ans,max(0,m-dis[s1,t1]-dis[s2,t2])); 58 for i:=1 to n do 59 for j:=1 to n do 60 begin 61 if (dis[i,s1]+dis[i,j]+dis[j,t1]<=h1)and(dis[i,s2]+dis[i,j]+dis[j,t2]<=h2) then 62 ans:=max(ans,m-dis[i,s1]-dis[i,s2]-dis[i,j]-dis[j,t1]-dis[j,t2]); 63 if (dis[i,s1]+dis[i,j]+dis[j,t1]<=h1)and(dis[i,t2]+dis[i,j]+dis[j,s2]<=h2) then 64 ans:=max(ans,m-dis[i,s1]-dis[i,t2]-dis[i,j]-dis[j,s2]-dis[j,t1]); 65 end; 66 for i:=1 to n do 67 for j:=1 to n do if (dis[i,s1]+dis[i,t1]<=h1)and(dis[j,t2]+dis[j,s2]<=h2) then 68 ans:=max(ans,max(0,m-dis[i,s1]-dis[i,t1]-dis[j,s2]-dis[j,t2])); 69 if (h1>=dis[s1,t1])and(h2>=dis[s2,t2]) then ans:=max(ans,m-h1-h2); 70 writeln(ans); 71 end.
543C. Remembering Strings
You have multiset of n strings of the same length, consisting of lowercase English letters. We will say that those strings are easy to remember if for each string there is some position i and some letter c of the English alphabet, such that this string is the only string in the multiset that has letter c in position i .
For example, a multiset of strings {"abc", "aba", "adc", "ada"} are not easy to remember. And multiset {"abc", "ada", "ssa"} is easy to remember because:
You want to change your multiset a little so that it is easy to remember. For a ij coins, you can change character in the j -th position of the i -th string into any other lowercase letter of the English alphabet. Find what is the minimum sum you should pay in order to make the multiset of strings easy to remember.
我们可以从任意一位未满足题意的字符串操作,然而又要保证所有的为满足题意的字符串都被操作过
很显然:如果当前位置是这一列中独一无二的字符,直接向下面的状态转移当前所得的最优解
但是有一种优秀的处理方法:就是假设一列中某个字符出现了x次,如果其余x-1个字符都修改掉了,剩下一个也就独一无二了
显然,向下转移的状态是把这些位置都更新成满足题意,花费为总花费-最大花费
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 const int maxn=22,INF=1000000007,maxm=1100010; 5 struct node{ 6 int tot,sum,mx,cov; 7 }a[maxn][maxn]; 8 int n,m,f[maxm],len[maxm],q[maxm],tot[200],sum[200],mx[200],cov[200],map[maxn][maxn],p[maxn][maxn]; 9 char s[100]; 10 int calc(int x){ 11 int ans=0; 12 for (;x;x=x>>1) ans+=x&1; 13 return ans; 14 } 15 16 int max(int a,int b){ 17 if (a>b) return a; 18 return b; 19 } 20 21 int min(int a,int b){ 22 if (a<b) return a; 23 return b; 24 } 25 26 int getf(int x){ 27 for (int i=1;i<=n;i++){ 28 if ((x&1)==0) return (n-i+1); 29 x=x >> 1; 30 } 31 } 32 void sortf(int l,int r){ 33 int i=l,j=r,mid=len[(l+r)>>1]; 34 do{ 35 while (i<r&&len[i]<mid) i++; 36 while (l<j&&len[j]>mid) j--; 37 if (i<=j){ 38 len[0]=len[i];len[i]=len[j];len[j]=len[0]; 39 q[0]=q[i];q[i]=q[j];q[j]=q[0]; 40 i++;j--; 41 } 42 }while (i<=j); 43 if (i<r) sortf(i,r); 44 if (l<j) sortf(l,j); 45 } 46 47 int main(){ 48 scanf("%d%d",&n,&m);gets(s); 49 char ch; 50 for (int i=1;i<=n;i++){ 51 for (int j=1;j<=m;j++){ 52 scanf("%c",&ch); 53 map[i][j]=ch; 54 } 55 gets(s); 56 } 57 for (int i=1;i<=n;i++) 58 for (int j=1;j<=m;j++) scanf("%d",&p[i][j]); 59 for (int i=1;i<=m;i++){ 60 memset(cov,0,sizeof(cov)); 61 memset(sum,0,sizeof(sum)); 62 memset(mx,0,sizeof(mx)); 63 memset(tot,0,sizeof(tot)); 64 for (int j=1;j<=n;j++){ 65 int ch=map[j][i]; 66 cov[ch]+=1 << (n-j); 67 sum[ch]+=p[j][i]; 68 mx[ch]=max(mx[ch],p[j][i]); 69 tot[ch]++; 70 } 71 for (int j=1;j<=n;j++){ 72 int ch=map[j][i]; 73 a[j][i].cov=cov[ch]; 74 a[j][i].sum=sum[ch]; 75 a[j][i].mx=mx[ch]; 76 a[j][i].tot=tot[ch]; 77 } 78 } 79 for (int i=0;i<=(1<<n)-2;i++) q[i+1]=i,len[i+1]=calc(q[i+1]); 80 sortf(1,(1<<n)-1); 81 memset(f,INF,sizeof(f)); 82 f[0]=0; 83 for (int i=1;i<=(1<<n)-1;i++)if (f[q[i]]!=f[maxm-1]){ 84 int x=getf(q[i]); 85 for (int j=1;j<=m;j++){ 86 if (a[x][j].tot==1) f[q[i]|(1<<(n-x))]=min(f[q[i]|(1<<(n-x))],f[q[i]]); 87 else{ 88 f[q[i]|(1<<(n-x))]=min(f[q[i]|(1<<(n-x))],f[q[i]]+p[x][j]); 89 f[q[i]|a[x][j].cov]=min(f[q[i]|a[x][j].cov],f[q[i]]+a[x][j].sum-a[x][j].mx); 90 } 91 } 92 } 93 printf("%d/n",f[(1<<n)-1]); 94 return 0; 95 }
543D. Road Improvement
The country has n cities and n - 1 bidirectional roads, it is possible to get from every city to any other one if you move only along the roads. The cities are numbered with integers from 1 to n inclusive.
All the roads are initially bad, but the government wants to improve the state of some roads. We will assume that the citizens are happy about road improvement if the path from the capital located in city x to any other city contains at most one bad road.
Your task is — for every possible x determine the number of ways of improving the quality of some roads in order to meet the citizens' condition. As those values can be rather large, you need to print each value modulo 1 000 000 007 ( 10 9 + 7).
就这棵子树而言,除了下面的答案外,将连接子树与父亲节点的边毁掉也是一种方案,因此+1
刚开始问自己:不是应该枚举一下有几棵子树要毁掉,分别毁掉哪几棵子树吗?那样复杂度就呵呵了啊...
但是在我们第二次dfs计算上面部分的答案的时候,要将当前子树对父亲节点的贡献除掉
增加一个标记vis,表示在向下的答案中出现的因子为模数的个数
因为如果儿子节点的答案中有模数这个因子了,那么它对父亲的贡献=1,相当于不变
如果当前节点的vis>0也就是有模数这个因子的话,我们是没有统计它对父亲的答案的
当前节点的vis=0
否则,也就是父亲节点中除了当前节点的贡献之外还有别的模数因子,此时答案为1
1 const maxn = 400010;ttt = 10007; 2 var n,e,i,j,x:longint; 3 fa,next,link,vis:array[-1..maxn]of longint; 4 a:array[-1..maxn]of record sum,sum2,x1,x2:int64;end; 5 tt:int64; 6 7 procedure add(x,y:longint); 8 begin 9 inc(e);fa[e]:=y;next[e]:=link[x];link[x]:=e; 10 inc(e);fa[e]:=x;next[e]:=link[y];link[y]:=e; 11 end; 12 13 procedure ex_Euclid(a,b:int64;var x,y:int64); 14 var t:int64; 15 begin 16 if b=0 then 17 begin 18 x:=1;y:=0; 19 exit; 20 end else 21 begin 22 ex_Euclid(b,a mod b,x,y); 23 t:=x;x:=y;y:=t-(a div b)*y; 24 end; 25 end; 26 27 function inverse(a:int64):int64; 28 var x,y:int64; 29 begin 30 ex_Euclid(a,tt,x,y); 31 while x<0 do inc(x,tt); 32 exit(x); 33 end; 34 35 procedure dfs1(p:longint); 36 var j:longint; 37 begin 38 a[p].sum:=1;vis[p]:=1; 39 j:=link[p]; 40 while j<>0 do 41 begin 42 if vis[fa[j]]=0 then 43 begin 44 dfs1(fa[j]); 45 if a[fa[j]].x1=0 then 46 begin 47 if a[fa[j]].sum+1=tt then inc(a[p].x1) else 48 a[p].sum:=(a[p].sum*(a[fa[j]].sum+1))mod tt; 49 end; 50 end; 51 j:=next[j]; 52 end; 53 end; 54 55 procedure dfs2(fat,p:longint); 56 var j:longint; 57 begin 58 vis[p]:=2; 59 if fat<>0 then 60 begin 61 if a[p].x1<>0 then 62 begin 63 if a[fat].x1=0 then a[p].sum2:=(a[fat].sum2*a[fat].sum+1) mod tt 64 else a[p].sum2:=1; 65 end else 66 begin 67 if a[p].sum+1=tt then 68 begin 69 if a[fat].x1>1 then a[p].sum2:=1 else 70 a[p].sum2:=(a[fat].sum2*a[fat].sum+1) mod tt; 71 end else 72 begin 73 if a[fat].x1>0 then a[p].sum2:=1 else 74 a[p].sum2:=(a[fat].sum2*a[fat].sum mod tt*inverse(a[p].sum+1)+1) mod tt; 75 end; 76 end; 77 end else a[p].sum2:=1; 78 j:=link[p]; 79 while j<>0 do 80 begin 81 if vis[fa[j]]=1 then 82 dfs2(p,fa[j]); 83 j:=next[j]; 84 end; 85 end; 86 87 begin 88 tt:=1000000007; 89 readln(n);tt:=tt; 90 e:=0; 91 for i:=2 to n do 92 begin 93 read(x);add(i,x); 94 end; 95 fillchar(vis,sizeof(vis),0); 96 dfs1(1);dfs2(0,1); 97 tt:=tt; 98 for i:=1 to n do if a[i].x1>0 then a[i].sum:=0; 99 for i:=1 to n-1 do write((a[i].sum*a[i].sum2) mod tt,' '); 100 writeln(a[n].sum*a[n].sum2 mod tt); 101 end.