2015_12

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77250#problem/L password123　　

L - City

给n*m的矩阵，矩阵的值表示该格点有共多少条边，边是相邻两个格点之间，相邻是上下左右四个方向。矩阵中只有一个-1，要求这个点的边数。

做法，通过i+j的奇偶可以将矩阵分成两个部分，就像国际象棋盘，然后对于一条边，它会对奇数部分贡献1，对偶数部分贡献1，所以统计一下黑格子，白格子的和，他们应该相等。

所以差值就是-1的格子的边数。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 int main(){
 4     int t,n,m,x;
 5     while(~scanf("%d",&t)){
 6         while(t--){
 7             scanf("%d%d",&n,&m);
 8             int s1=0,s2=0;
 9             for(int i=0;i<n;i++){
10                 for(int j=0;j<m;j++){
11                     scanf("%d",&x);
12                     if(x==-1) continue;
13                     if((i+j)&1){
14                         s1+=x;
15                     }
16                     else{
17                         s2+=x;
18                     }
19                 }
20             }
21             printf("%d
",abs(s1-s2));
22         }
23     }
24     return 0;
25 }

View Code

K - Concert Tour

有n个城市，一共工作m天，输入一个n*m的矩阵，get【i】【j】表示在 i 城市在第 j 天工作能挣的钱，再输入cost矩阵 cost i j ，表示 i 城市到 j 城市的花费。

用dp i j 表示第j 天在 i 工作所能获得的最大钱

第一天去某个城市是不花钱的，所以dp 【i】【1】就是get

枚举天数，对每一天枚举所在城市，这个状态可以推到n个状态，因为下一天可以去任意一个城市，

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int M=1e2+10;
 5 const int inf=0x3f3f3f3f;
 6 int get[M][64];
 7 int cost[M][M];
 8 int dp[M][64];
 9 int main(){
10     int t,n,m;
11     while(~scanf("%d",&t)){
12         while(t--){
13             scanf("%d%d",&n,&m);
14             for(int i=1;i<=n;i++){
15                 for(int j=1;j<=m;j++){
16                     scanf("%d",&get[i][j]);
17                     dp[i][j]=-inf;
18                 }
19             }
20             for(int i=1;i<=n;i++){
21                 for(int j=1;j<=n;j++){
22                     scanf("%d",&cost[i][j]);
23                 }
24             }
25             for(int i=1;i<=n;i++){
26                 dp[i][1]=get[i][1];
27             }
28             for(int j=1;j<=m;j++){
29                 for(int i=1;i<=n;i++){
30                     for(int k=1;k<=n;k++){
31                         dp[k][j+1]=max(dp[k][j+1],dp[i][j]+get[k][j+1]-cost[i][k]);
32                     }
33                 }
34             }
35             int ans=-inf;
36             for(int i=1;i<=n;i++){
37                 ans=max(ans,dp[i][m]);
38             }
39             printf("%d
",ans);
40         }
41     }
42     return 0;
43 }

View Code

J - Blanket

m个人，下标0——m-1，有n次覆盖，每次输入a，b，所有下标%b《a的人覆盖一次，最后输出被覆盖0到n次的人数

a，b都是16，n次操作重复的很多，统计一下，最后就是16*16个覆盖，但是次数可能多次，

然后就是区间累加了，左++右--的方法

 1 #include<cstdio>
 2 #include<cstring>
 3 #define mt(a,b) memset(a,b,sizeof(a))
 4 const int M=1e6+10;
 5 int mat[32][32];
 6 int dp[M];
 7 int ans[M];
 8 int main(){
 9     int t,n,m,a,b;
10     while(~scanf("%d",&t)){
11         while(t--){
12             scanf("%d%d",&n,&m);
13             mt(mat,0);
14             for(int i=0;i<n;i++){
15                 scanf("%d%d",&a,&b);
16                 mat[a][b]++;
17             }
18             for(int i=0;i<m;i++){
19                 dp[i]=0;
20             }
21             for(a=1;a<=16;a++){
22                 for(b=a;b<=16;b++){
23                     int cnt=mat[a][b];
24                     if(!cnt) continue;
25                     if(b==1){
26                         dp[0]+=cnt;
27                         continue;
28                     }
29                     int id=0;
30                     while(id<m){
31                         dp[id]+=cnt;
32                         if(id+a<m){
33                             dp[id+a]-=cnt;
34                         }
35                         id+=b;
36                     }
37                 }
38             }
39             int val=0;
40             for(int i=0;i<=n;i++){
41                 ans[i]=0;
42             }
43             for(int i=0;i<m;i++){
44                 val+=dp[i];
45                 ans[val]++;
46             }
47             for(int i=0;i<=n;i++){
48                 printf("%d
",ans[i]);
49             }
50         }
51     }
52     return 0;
53 }

View Code

I - The Programmers

p 个人，s个城市，c是每个城市能容纳的参赛人数，m是边数，输入m对u，v，表示u人能去v城市比赛。

就是个二分图最大匹配，如果c==1，那就是最简单的二分匹配，现在是c，用最大流解最大匹配的建图源点到每个人，人到城市（输入），都是流量1，城市到汇点，都是流量c

最大流就是最大匹配数。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 const int inf=0x3f3f3f3f;
  7 class Dinic { ///最大流 O(MV^2*ME)
  8     typedef int typef;///流量的类型
  9     static const int ME=1e6+10;///边的个数
 10     static const int MV=1e3+10;///点的个数
 11     int temp[MV],cur[MV],level[MV],path[MV];
 12     bool used[MV];
 13     queue<int> q;
 14     typef flow;
 15     bool bfs(int s,int t) {
 16         mt(level,-1);
 17         while(!q.empty()) q.pop();
 18         q.push(s);
 19         level[s]=1;
 20         while(!q.empty()) {
 21             int u=q.front();
 22             q.pop();
 23             for(int i=g.head[u]; ~i; i=g.e[i].next) {
 24                 int v=g.e[i].v;
 25                 if(level[v]==-1&&g.e[i].flow) {
 26                     level[v]=level[u]+1;
 27                     q.push(v);
 28                     if(v==t) return true;
 29                 }
 30             }
 31         }
 32         return false;
 33     }
 34     struct G {
 35         struct E {
 36             int u,v,next;
 37             typef flow;
 38         } e[ME];
 39         int le,head[MV];
 40         void init() {
 41             le=0;
 42             mt(head,-1);
 43         }
 44         void add(int u,int v,typef flow) {
 45             e[le].u=u;
 46             e[le].v=v;
 47             e[le].flow=flow;
 48             e[le].next=head[u];
 49             head[u]=le++;
 50         }
 51     } g;
 52 public:
 53     typef getflow() {
 54         return flow;
 55     }
 56     void init() {
 57         g.init();
 58     }
 59     void add(int u,int v,typef flow) {
 60         g.add(u,v,flow);
 61         g.add(v,u,0);
 62     }
 63     void solve(int s,int t) {
 64         int p,tempp;
 65         typef now;
 66         bool flag;
 67         flow=0;
 68         while(bfs(s,t)) {
 69             for(int i=0; i<MV; i++) {
 70                 temp[i]=g.head[i];
 71                 used[i]=true;
 72             }
 73             p=1;
 74             path[p]=s;
 75             while(p) {
 76                 int u=path[p];
 77                 if(u==t) {
 78                     now=inf;
 79                     for(int i=1; i<p; i++) {
 80                         now=min(now,g.e[cur[path[i]]].flow);
 81                     }
 82                     flow+=now;
 83                     for(int i=1; i<p; i++) {
 84                         int j=cur[path[i]];
 85                         g.e[j].flow-=now;
 86                         g.e[j^1].flow+=now;
 87                         if(!g.e[j].flow) tempp=i;
 88                     }
 89                     p=tempp;
 90                 } else {
 91                     flag=false;
 92                     for(int i=temp[u]; ~i; i=g.e[i].next) {
 93                         int v=g.e[i].v;
 94                         if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) {
 95                             cur[u]=i;
 96                             temp[u]=g.e[i].next;
 97                             flag=true;
 98                             path[++p]=v;
 99                             break;
100                         }
101                     }
102                     if(flag) continue;
103                     p--;
104                     used[u]=false;
105                 }
106             }
107         }
108     }
109 } g;
110 int main(){
111     int t,P,S,C,m,u,v;
112     while(~scanf("%d",&t)){
113         while(t--){
114             scanf("%d%d%d%d",&P,&S,&C,&m);
115             g.init();
116             int start=0,to=P+S+1;
117             while(m--){
118                 scanf("%d%d",&u,&v);
119                 g.add(u,v+P,1);
120             }
121             for(int i=1;i<=P;i++){
122                 g.add(start,i,1);
123             }
124             for(int i=1;i<=S;i++){
125                 g.add(i+P,to,C);
126             }
127             g.solve(start,to);
128             printf("%d
",g.getflow());
129         }
130     }
131     return 0;
132 }

View Code

E - Zeroes

定义 fzero 是一个数阶乘最后0的个数输入 LR，问L到R之间的数，他们的fzero有多少种不同的值

打表发现每遇到一个5的倍数，就会多一种，那就算一下LR之间有多少个5的倍数了

 1 #include<cstdio>
 2 typedef unsigned long long LL;
 3 LL l,r;
 4 int main(){
 5     while(~scanf("%llu%llu",&l,&r),l|r){
 6         while(true){
 7             if(l%5==0) break;
 8             l--;
 9         }
10         while(true){
11             if(r%5==0) break;
12             r--;
13         }
14         printf("%llu
",(r-l)/5+1);
15     }
16     return 0;
17 }

View Code

B - Combination

求 n个中选 i 个的情况数中奇数的个数，其中 i 从0-n，n从 l 到 r ，l r 输入

打表，lmh推出的前n项和公式分奇偶两种，然后我根据公式直接dfs，加记忆化勉强卡过

 1 #include<cstdio>
 2 #include<map>
 3 using namespace std;
 4 typedef unsigned long long LL;
 5 map<LL,LL> mp;
 6 LL dfs(LL x){
 7     if(x==0) return 0;
 8     LL res=mp[x];
 9     if(res) return res;
10     if(x&1){
11         res=2*dfs(x/2)+dfs(x/2+1);
12     }
13     else{
14         res=3*dfs(x/2);
15     }
16     mp[x]=res;
17     return res;
18 }
19 LL L,R;
20 int main(){
21     mp.clear();
22     mp[1]=1;
23     while(~scanf("%llu%llu",&L,&R),L|R){
24         printf("%llu
",dfs(R+1)-dfs(L));
25     }
26     return 0;
27 }

View Code

A - Volume Control

输入n，问 0-n任选两个数共有多少种不同的乘积，

首先，有单调性，n越大，能生成的乘积越多，并且小的值能生成的，大的值一定能

所以可以维护一个9e8的bool数组表示是否出现过，从小到大处理，这样处理大的值的时候，之前小的值生成的标记就利用起来了听所vector《bool》是按位的还可以（maxn）长知识

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 vector<bool> v(900000010);
 5 int ans[30010];
 6 int main(){
 7     v.clear();
 8     int tmp=1;
 9     for(int i=1;i<=30000;i++){
10         for(int j=1;j<=i;j++){
11             int mul=i*j;
12             if(!v[mul]){
13                 tmp++;
14                 v[mul]=true;
15             }
16         }
17         ans[i]=tmp;
18     }
19     int t,n;
20     while(~scanf("%d",&t)){
21         while(t--){
22             scanf("%d",&n);
23             printf("%d
",ans[n]);
24         }
25     }
26     return 0;
27 }

View Code

end