Codeforces Round #525 (Div. 2)-A/B/C/E

http://codeforces.com/contest/1088/problem/A

暴力一波就好了。

//题解有O(1)做法是 (n-n%2,2)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<map>
 5 #include<set>
 6 #include<stack>
 7 #include<deque>
 8 #include<bitset>
 9 #include<unordered_map>
10 #include<unordered_set>
11 #include<queue>
12 #include<cstdlib>
13 #include<ctype.h>
14 #include<ctime>
15 #include<functional>
16 #include<algorithm>
17 #include<bits/stdc++.h>
18 using namespace std;
19 #define LL long long 
20 #define pii pair<int,int>
21 #define mp make_pair
22 #define pb push_back
23 #define fi first
24 #define se second
25 #define inf 0x3f3f3f3f
26 #define debug puts("debug")
27 #define mid ((L+R)>>1)
28 #define lc (id<<1)
29 #define rc (id<<1|1)
30 const int maxn=200020;
31 const int maxm=200020;
32 const double PI=acos(-1.0);
33 const double eps=1e-6;
34 const LL mod=1e9+7;
35 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
36 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
37 LL qpow(LL a,LL b,LL c){LL r=1; for(;b;b>>=1,a=a*a%c)if(b&1)r=r*a%c;return r;}
38 template<class T>
39 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
40 struct Edge{int u,v,w,next;};
41 int main(){
42     int t,n,m,i,j,k,u,v;
43     int ans=-1;
44     cin>>n;
45     for(i=1;i<=n;++i){
46         for(j=1;j<=n;++j){
47             if(i%j==0&&i*j>n&&i/j<n){
48                 cout<<i<<' '<<j<<endl;
49                 return 0;
50             }
51         }
52     }
53     cout<<ans<<endl;
54     return 0;
55 }

http://codeforces.com/contest/1088/problem/B

排下序然后遍历一遍。容易发现被减数总等于前一个a[i]。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<map>
 5 #include<set>
 6 #include<stack>
 7 #include<deque>
 8 #include<bitset>
 9 #include<unordered_map>
10 #include<unordered_set>
11 #include<queue>
12 #include<cstdlib>
13 #include<ctype.h>
14 #include<ctime>
15 #include<functional>
16 #include<algorithm>
17 #include<bits/stdc++.h>
18 using namespace std;
19 #define LL long long 
20 #define pii pair<int,int>
21 #define mp make_pair
22 #define pb push_back
23 #define fi first
24 #define se second
25 #define inf 0x3f3f3f3f
26 #define debug puts("debug")
27 #define mid ((L+R)>>1)
28 #define lc (id<<1)
29 #define rc (id<<1|1)
30 const int maxn=200020;
31 const int maxm=200020;
32 const double PI=acos(-1.0);
33 const double eps=1e-6;
34 const LL mod=1e9+7;
35 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
36 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
37 LL qpow(LL a,LL b,LL c){LL r=1; for(;b;b>>=1,a=a*a%c)if(b&1)r=r*a%c;return r;}
38 template<class T>
39 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
40 struct Edge{int u,v,w,next;};
41 int a[maxn];
42 int main(){
43     int t,n,m,i,j,k,u,v;
44     cin>>n>>k;
45     for(i=1;i<=n;++i)scanf("%d",a+i);
46     sort(a+1,a+1+n);
47     int d=0;
48     for(i=1,j=1;i<=n&&k;i++){
49         if(a[i]-d==0)continue;
50         printf("%d
",a[i]-d);
51         k--;
52         d=a[i];
53     }
54     while(k--)puts("0");
55     return 0;
56 }

http://codeforces.com/contest/1088/problem/C

构造，题目里的n+1就是提示了，从n-1开始倒着遍历，进行n次加法每次都让当前的数%n等于i,最后摸一次n就好。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<map>
 5 #include<set>
 6 #include<stack>
 7 #include<deque>
 8 #include<bitset>
 9 #include<unordered_map>
10 #include<unordered_set>
11 #include<queue>
12 #include<cstdlib>
13 #include<ctype.h>
14 #include<ctime>
15 #include<functional>
16 #include<algorithm>
17 #include<bits/stdc++.h>
18 using namespace std;
19 #define LL long long 
20 #define pii pair<int,int>
21 #define mp make_pair
22 #define pb push_back
23 #define fi first
24 #define se second
25 #define inf 0x3f3f3f3f
26 #define debug puts("debug")
27 #define mid ((L+R)>>1)
28 #define lc (id<<1)
29 #define rc (id<<1|1)
30 const int maxn=200020;
31 const int maxm=200020;
32 const double PI=acos(-1.0);
33 const double eps=1e-6;
34 const LL mod=1e9+7;
35 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
36 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
37 LL qpow(LL a,LL b,LL c){LL r=1; for(;b;b>>=1,a=a*a%c)if(b&1)r=r*a%c;return r;}
38 template<class T>
39 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
40 struct Edge{int u,v,w,next;};
41 LL a[maxn];
42 LL op[maxn],p1[maxn],p2[maxn],tot=0;
43 int main(){
44     int t,n,m,i,j,k,u,v;
45     cin>>n;
46     for(i=0;i<n;++i)scanf("%lld",a+i);
47     LL d=0;
48     for(i=n-1;i>=0;--i){
49         if((a[i]+d)%n==i)continue;
50         else{
51             LL x=(a[i]+d)%n;
52             LL delta=(i-x+n)%n;
53             d+=delta;
54             op[tot]=1;
55             p1[tot]=i+1;
56             p2[tot]=delta;
57             tot++;
58         }
59     }
60     op[tot]=2;
61     p1[tot]=p2[tot]=n;
62     tot++;
63     cout<<tot<<endl;
64     for(i=0;i<tot;++i){
65         printf("%lld %lld %lld
",op[i],p1[i],p2[i]);
66     }
67     return 0;
68 }

http://codeforces.com/contest/1088/problem/E

给出一棵树，每个节点有权值a[i]，找出k个互不重复覆盖的联通分量，使得SUM{a[i] | i in s} / k的值最大化，如果有多种方案选择k最大的方案。

假设最优解是{b1,b2...bk} 那么有公式 max{b}>=ave{b} ,也就是说ave{b}的最大值就是max{b},问题转化为求最大权值和的连通分量，然后看有多少个等于ans的联通分量，就是k。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<map>
 5 #include<set>
 6 #include<stack>
 7 #include<deque>
 8 #include<bitset>
 9 #include<unordered_map>
10 #include<unordered_set>
11 #include<queue>
12 #include<cstdlib>
13 #include<ctype.h>
14 #include<ctime>
15 #include<functional>
16 #include<algorithm>
17 #include<bits/stdc++.h>
18 using namespace std;
19 #define LL long long 
20 #define pii pair<int,int>
21 #define mp make_pair
22 #define pb push_back
23 #define fi first
24 #define se second
25 #define inf 0x3f3f3f3f
26 #define debug puts("debug")
27 #define mid ((L+R)>>1)
28 #define lc (id<<1)
29 #define rc (id<<1|1)
30 const int maxn=300020;
31 const int maxm=200020;
32 const double PI=acos(-1.0);
33 const double eps=1e-6;
34 const LL mod=1e9+7;
35 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
36 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
37 LL qpow(LL a,LL b,LL c){LL r=1; for(;b;b>>=1,a=a*a%c)if(b&1)r=r*a%c;return r;}
38 template<class T>
39 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
40 struct Edge{int u,v,w,next;};
41 LL ans=-inf,f[maxn],a[maxn],k=0;
42 vector<int>g[maxn]; 
43 void dfs(int u,int fa,bool o){
44     f[u]=a[u];
45     for(int v:g[u]){
46         if(v!=fa){
47             dfs(v,u,o);
48             if(f[v]>0) f[u]+=f[v];
49         }
50     }
51     if(o)ans=max(ans,f[u]);
52     if(!o){
53         if(f[u]==ans){
54             k++;
55             f[u]=0;
56         }
57     }
58 }
59 int main(){
60     int t,n=0,m,i=0,j,u,v;
61     scanf("%d",&n);
62     for(i=1;i<=n;++i)scanf("%lld",a+i);
63     for(i=1;i<n;++i){
64         scanf("%d%d",&u,&v);
65         g[u].pb(v),g[v].pb(u);
66     }
67     dfs(1,0,1);
68     dfs(1,0,0);
69     printf("%lld %lld
",ans*k,k);
70     return 0;
71 }