http://codeforces.com/contest/1088/problem/A
暴力一波就好了。
//题解有O(1)做法是 (n-n%2,2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<deque>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<cstdlib>
#include<ctype.h>
#include<ctime>
#include<functional>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define debug puts("debug")
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (id<<1|1)
const int maxn=;
const int maxm=;
const double PI=acos(-1.0);
const double eps=1e-;
const LL mod=1e9+;
LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}
template<class T>
void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
struct Edge{int u,v,w,next;};
int main(){
int t,n,m,i,j,k,u,v;
int ans=-;
cin>>n;
for(i=;i<=n;++i){
for(j=;j<=n;++j){
if(i%j==&&i*j>n&&i/j<n){
cout<<i<<' '<<j<<endl;
return ;
}
}
}
cout<<ans<<endl;
return ;
}
http://codeforces.com/contest/1088/problem/B
排下序然后遍历一遍。容易发现被减数总等于前一个a[i]。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<deque>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<cstdlib>
#include<ctype.h>
#include<ctime>
#include<functional>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define debug puts("debug")
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (id<<1|1)
const int maxn=;
const int maxm=;
const double PI=acos(-1.0);
const double eps=1e-;
const LL mod=1e9+;
LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}
template<class T>
void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
struct Edge{int u,v,w,next;};
int a[maxn];
int main(){
int t,n,m,i,j,k,u,v;
cin>>n>>k;
for(i=;i<=n;++i)scanf("%d",a+i);
sort(a+,a++n);
int d=;
for(i=,j=;i<=n&&k;i++){
if(a[i]-d==)continue;
printf("%d\n",a[i]-d);
k--;
d=a[i];
}
while(k--)puts("");
return ;
}
http://codeforces.com/contest/1088/problem/C
构造，题目里的n+1就是提示了，从n-1开始倒着遍历，进行n次加法每次都让当前的数%n等于i,最后摸一次n就好。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<deque>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<cstdlib>
#include<ctype.h>
#include<ctime>
#include<functional>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define debug puts("debug")
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (id<<1|1)
const int maxn=;
const int maxm=;
const double PI=acos(-1.0);
const double eps=1e-;
const LL mod=1e9+;
LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}
template<class T>
void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
struct Edge{int u,v,w,next;};
LL a[maxn];
LL op[maxn],p1[maxn],p2[maxn],tot=;
int main(){
int t,n,m,i,j,k,u,v;
cin>>n;
for(i=;i<n;++i)scanf("%lld",a+i);
LL d=;
for(i=n-;i>=;--i){
if((a[i]+d)%n==i)continue;
else{
LL x=(a[i]+d)%n;
LL delta=(i-x+n)%n;
d+=delta;
op[tot]=;
p1[tot]=i+;
p2[tot]=delta;
tot++;
}
}
op[tot]=;
p1[tot]=p2[tot]=n;
tot++;
cout<<tot<<endl;
for(i=;i<tot;++i){
printf("%lld %lld %lld\n",op[i],p1[i],p2[i]);
}
return ;
}
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。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<deque>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<cstdlib>
#include<ctype.h>
#include<ctime>
#include<functional>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define debug puts("debug")
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (id<<1|1)
const int maxn=;
const int maxm=;
const double PI=acos(-1.0);
const double eps=1e-;
const LL mod=1e9+;
LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}
template<class T>
void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
struct Edge{int u,v,w,next;};
LL ans=-inf,f[maxn],a[maxn],k=;
vector<int>g[maxn];
void dfs(int u,int fa,bool o){
f[u]=a[u];
for(int v:g[u]){
if(v!=fa){
dfs(v,u,o);
if(f[v]>) f[u]+=f[v];
}
}
if(o)ans=max(ans,f[u]);
if(!o){
if(f[u]==ans){
k++;
f[u]=;
}
}
}
int main(){
int t,n=,m,i=,j,u,v;
scanf("%d",&n);
for(i=;i<=n;++i)scanf("%lld",a+i);
for(i=;i<n;++i){
scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
}
dfs(,,);
dfs(,,);
printf("%lld %lld\n",ans*k,k);
return ;
}