Codeforces Round #304 (Div. 2)

飞来迟到的题解：

来自火星的铭文：由于蒟蒻，所以不断补题；

A:手速题；

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<bits/stdc++.h>
 4 using  namespace std;
 5 typedef long long ll;
 6 
 7 int  main()
 8 {
 9     ll k,n,w;
10     cin>>k>>n>>w;
11     ll ans=0;
12     for (int i=1;i<=w;i++)
13     {
14         if (n>=k*i)
15         {
16             n-=k*i;
17         }
18         else
19         {
20             ans+=k*i-n;
21             n=0;
22         }
23     }
24     cout<<ans;
25     return 0;
26 }

View Code

B:我居然挂了。。

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<bits/stdc++.h>
 4 using  namespace std;
 5 typedef long long ll;
 6 
 7 
 8 int a[3333];
 9 int  main()
10 {
11     int n;
12     cin>>n;
13     for (int i=1;i<=n;i++) cin>>a[i];
14     sort(a+1,a+n+1);
15     int ans=0;
16     for (int  i=1;i<=n;i++)
17     {
18         for (int j=i+1;j<=n;j++)
19         if (a[j]==a[j-1])
20         {
21             ans++;
22             a[j]++;
23         }
24     }
25     cout<<ans;
26     return 0;

View Code

我从前推后面，迭代N次，但是应该注意加的顺序。

C:不知道规律是啥，所以写了一个报了暴力，设置了一个循环结束时间t,没有然后了。

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<bits/stdc++.h>
 4 using  namespace std;
 5 typedef long long ll;
 6 
 7 
 8 int a[233333],b[233333];
 9 int  main()
10 {
11     int n,k1,k2;
12     cin>>n>>k1;
13 
14     for (int i=1;i<=k1;i++) cin>>a[i];
15     cin>>k2;
16     for (int j=1;j<=k2;j++) cin>>b[j];
17 
18     int h1=1,t1=k1;
19     int h2=1,t2=k2;
20 
21     int idx=0;
22     while (1)
23     {
24         idx++;
25         if (idx>213456) break;
26         if (h1>t1)
27         {
28             idx--;
29             cout<<idx<<" "<<2;
30             return 0;
31         }
32         if (h2>t2)
33         {
34             idx--;
35             cout<<idx<<" "<<1;
36             return 0;
37         }
38         if (a[h1]>b[h2])
39         {
40 
41             a[++t1]=b[h2];
42             a[++t1]=a[h1];
43         }
44         else
45         {
46 
47             b[++t2]=a[h1];
48             b[++t2]=b[h1];
49         }
50            h2++;
51             h1++;
52        // cout<<h1<<" "<<t1<<endl;
53       //  cout<<h2<<" "<<t2<<endl;
54     }
55     cout<<-1;
56     return 0;
57 }

View Code

D:大概是求一个数的素数因子有多少，再求一下前缀和--->这些都是预处理，

然后询问

 1 #include<bits/stdc++.h>
 2 using  namespace std;
 3 typedef long long ll;
 4 #define N 5000005
 5 ll dp[N];
 6 int b[N];
 7 
 8 int pan(int x,int y)
 9 {
10    int ans=0;
11    while (y%x==0)
12    {
13        ans++;
14        y/=x;
15    }
16     return ans;
17 }
18 
19 
20 void init()
21 {
22     for (int i=2;i<N;i++)
23     {
24         if (!b[i]) {
25         b[i]=1;
26         for (int j=i+i;j<N;j+=i)//我判断的方法还是蛮奇特的，算暴力了。就是判断y%t^x==0,求出x
27         b[j]+=pan(i,j/i)+1;
28         }
29     }
30    // for (int i=10;i<=16;i++) cout<<b[i]<<endl;
31     for (int i=1;i<N;i++) dp[i]=dp[i-1]+b[i];
32   //  for (int i=1;i<=10;i++) cout<<dp[i]<<endl;
33 
34 }
35 
36 
37 int  main()
38 {
39 
40    init();
41    int t;
42    scanf("%d",&t);
43    while (t--)
44    {
45        int x,y;
46        scanf("%d%d",&x,&y);
47        printf("%I64d
",dp[x]-dp[y]);
48    }
49    return 0;
50 }

View Code

E: 这套题最有价值的题目了，

开始看出网络流，但是不会建图，因为我不会求一个点到另一个点的流量。

我们可以这样求流量，建图的时候，反向边流量都为0，然后流的流量都在反向边里面。

所以提出反向边的流量就可以了。

见图就是普通的几个见图方法。

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<iostream>
  5 #include<queue>
  6 
  7 using namespace std;
  8 
  9 #define N 25555
 10 #define inf 0x3f3f3f3f
 11 
 12 struct edge
 13 {
 14     int next,v,c;
 15 }e[N<<1];
 16 
 17 int n,m;
 18 int tot,head[N],d[N];
 19 
 20 void add(int u,int v,int c)
 21 {
 22     e[tot].v=v;
 23     e[tot].c=c;
 24     e[tot].next=head[u];
 25     head[u]=tot++;
 26 
 27     e[tot].v=u;
 28     e[tot].c=0;
 29     e[tot].next=head[v];
 30     head[v]=tot++;
 31 }
 32 
 33 int bfs(int s,int t)
 34 {
 35     memset(d,-1,sizeof(d));
 36     queue<int> q;
 37     q.push(s);
 38     d[s]=0;
 39 
 40     while (!q.empty())
 41     {
 42         int u=q.front();
 43         q.pop();
 44         if (u==t) return 1;
 45         for (int i=head[u];i!=-1;i=e[i].next)
 46         {
 47             int v=e[i].v;
 48             if (d[v]==-1&&e[i].c>0)
 49             {
 50                 d[v]=d[u]+1;
 51                 q.push(v);
 52             }
 53         }
 54     }
 55     return 0;
 56 }
 57 
 58 int dfs(int s,int t,int b)
 59 {
 60     int r=0;
 61     if (s==t) return b;
 62     for (int i=head[s];i!=-1&&r<b;i=e[i].next)
 63     {
 64         int v=e[i].v;
 65         if (e[i].c>0&&d[v]==d[s]+1)
 66         {
 67             int x=min(e[i].c,b-r);
 68             x=dfs(v,t,x);
 69             r+=x;
 70             e[i].c-=x;
 71             e[i^1].c+=x;
 72         }
 73     }
 74     if (!r) d[s]-=2;
 75     return r;
 76 }
 77 
 78 int dinic(int s,int t)
 79 {
 80     int ans=0,tmp;
 81     while (bfs(s,t))
 82     {
 83         while (tmp=(dfs(s,t,inf))) ans+=tmp;
 84     }
 85     return ans;
 86 }
 87 
 88 int a[222],b[222];
 89 int mp[222][222];
 90 
 91 
 92 int main()
 93 {
 94     memset(head,-1,sizeof(head));
 95 
 96     cin>>n>>m;
 97     int s=0,t=n+n+1;
 98     int tot=0;
 99     int tt=0;
100     for (int i=1;i<=n;i++) cin>>a[i],tot += a[i];
101     for (int i=1;i<=n;i++) cin>>b[i],tt += b[i];
102 
103     for (int i=1;i<=n;i++)
104     {
105        add(s,i,a[i]);
106        add(i+n,t,b[i]);
107        add(i,i+n,inf);
108     }
109 
110     while (m--)
111     {
112         int x,y;
113         cin>>x>>y;
114         add(x,y+n,inf );
115         add(y,x+n,inf );
116     }
117 
118     int ans=dinic(s,t);
119 
120 
121     if (ans!=tot||tot!=tt)
122     {
123         cout<<"NO";
124         return 0;
125     }
126     cout<<"YES"<<endl;
127     for (int i=1+n;i<=n+n;i++)
128     {
129      int v=i-n;
130      for (int j=head[i];j!=-1;j=e[j].next)
131      {
132          int u=e[j].v;
133        //  if (u<t)
134          mp[u][v]=e[j].c;
135      }
136     }
137 
138     for (int i=1;i<=n;i++)
139     {
140        for (int j=1;j<=n;j++) cout<<mp[i][j]<<" ";
141        cout<<endl;
142     }
143     return 0;
144 }

View Code