1001 Average
忍不住又补了一题。
只要枚举1与2之间1给2，2给1，什么都不做三种状态。
后面的情况都已经决定了。
（估计只有我比赛的时候把a candy当成a个糖果了吧QAQ）
# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;
typedef pair<int,int> pii;
typedef long long LL;
# define maxn
LL a[maxn],b[maxn],aver;
vector <pii> ans;
int n; void ans_print(void)
{
puts("YES");
printf("%d\n",ans.size());
for(int i=;i<ans.size();i++)
printf("%d %d\n",ans[i].first,ans[i].second);
return;
} bool judge(void)
{
for(int i=;i<n;i++)
{
if(a[i]==aver) continue;
if(a[i]==aver+)
{
a[i]--; a[i+]++;
ans.push_back(pii(i,i+));
continue;
}
if(a[i]==aver-&&a[i+]>)
{
a[i]++; a[i+]--;
ans.push_back(pii(i+,i));
continue;
}
memcpy(a,b,sizeof(a));
ans.clear();
return false;
}
if(a[n]==aver&&a[]==aver) return true;
if(a[n]==aver+&&a[]==aver-)
{
ans.push_back(pii(n,));
return true;
}
if(a[n]==aver-&&a[]==aver+)
{
ans.push_back(pii(,n));
return true;
}
memcpy(a,b,sizeof(a));
ans.clear();
return false;
} int main(void)
{
int T; cin>>T;
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",b+i);
LL sum=;
for(int i=;i<=n;i++) sum+=b[i];
if(sum%n) {puts("NO");continue;}
aver=sum/(LL)n;
memcpy(a,b,sizeof(a));
ans.clear();
if(a[]>aver+||a[]<aver-) {puts("NO");continue;}
if(judge()){ans_print(); continue;}
if(a[])
{
ans.push_back(pii(,));
a[]--; a[]++;
if(judge()){ans_print(); continue;}
}
if(a[])
{
ans.push_back(pii(,));
a[]++; a[]--;
if(judge()){ans_print(); continue;}
}
puts("NO");
}
return ;
}
Aguin
1002 Bipartite Graph
1003 Cake
还是把这个补了。
比赛的时候spj写错。放过了很多队（包括我们。
先搜出n<=40的所有情况。
搜索的时候先贪心的找最大的。
最大的不行的时候再找小一点的。这样很快能找到一组解。
其实在1-20内贪心的答案都是对……产生了可以贪的错觉。
第一组不能贪得情况是23 6 。
在20-40一共有9组不能贪的。所以挑挑出来也可以。
n>40的情况不停的取最后的2*m个数字，然后头尾配对放到m组里面。直到n<=40。
然后和之前做好的n<=40的情况合并就好了。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;
typedef long long LL;
vector<int> ans[][][];
vector<int> tem_ans[];
int n,m;
bool vis[]; bool dfs(int i,int rem,int each)
{
if(!rem&&i==m)
{
for(int i=;i<=m;i++)
{
for(int j=;j<tem_ans[i].size();j++)
{
int x=tem_ans[i][j];
ans[n][m][i].push_back(x);
}
tem_ans[i].clear();
}
return true;
}
if(!rem&&dfs(i+,each,each)) return true;
for(int pos=n;pos>;pos--)
{
if(!vis[pos]&&pos<=rem)
{
vis[pos]=;
tem_ans[i].push_back(pos);
if(dfs(i,rem-pos,each)) return true;
tem_ans[i].pop_back();
vis[pos]=;
}
}
return false;
} int main(void)
{
for(n=;n<=;n++)
{
for(m=;m<=;m++)
{
int sum=n*(n+)/,each=sum/m;
if(sum%m||n<*m-) continue;
memset(vis,,sizeof(vis));
dfs(,each,each);
}
}
int T; cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
LL sum=(LL)n*LL(n+)/,each=sum/m;
if(sum%m||n<*m-) {puts("NO"); continue;}
puts("YES");
for(int i=;i<=m;i++) tem_ans[i].clear();
while(n>)
{
for(int i=;i<=m;i++)
{
tem_ans[i].push_back(n-i+);
tem_ans[i].push_back(n-*m+i);
}
n-=*m;
}
for(int i=;i<=m;i++)
{
printf("%d",ans[n][m][i].size()+tem_ans[i].size());
for(int j=;j<ans[n][m][i].size();j++)
printf(" %d",ans[n][m][i][j]);
for(int j=;j<tem_ans[i].size();j++)
printf(" %d",tem_ans[i][j]);
puts("");
}
}
return ;
}
Aguin
1004 Deal
1005 Easy Sequence
1006 First One
终于补了这个。简直感动哭。
因为做法知道了。一直卡在边界。
后来直接把power[0]改成0。把[0,1),[1,2)合成[0,2)。
然后只有在区间左端点合法的时候再加tem。
# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
typedef long long LL;
# define maxn
LL sum[maxn],power[]; int main(void)
{
power[]=;
for(int i=;i<;i++) power[i]=power[i-]<<;
power[]=;
int T; cin>>T;
while(T--)
{
int n; scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%I64d",sum+i);
for(int i=;i<=n;i++) sum[i]+=sum[i-];
LL ans=;
for(int i=;i<;i++)
{
if(sum[n]<power[i]) break;
LL tem=,l=,r=;
for(int j=;j<=n;j++)
{
l=max(l,(LL)j);
while(l<n&&sum[l]-sum[j-]<power[i]) l++;
while(r<n&&sum[r+]-sum[j-]<power[i+]) r++;
if(sum[l]-sum[j-]>=power[i]) tem+=(l+r)*(r-l+)/+(r-l+)*(LL)j;
}
ans+=tem*(LL)(i+);
}
printf("%I64d\n",ans);
}
return ;
}
Aguin
1007 Group
1008 Hiking
先区间左端点升序排序。再以右端点为关键字搞个小根堆。
每次取右端点符合条件且最小的即可。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>
# include <vector>
using namespace std;
# define maxn
bool vis[maxn];
vector<int> ans; struct node
{
int id,l,r;
friend bool operator < (node a,node b)
{
return a.r>b.r;
}
} soda[maxn];
priority_queue <node> q; bool cmp(node a,node b)
{
return a.l<b.l;
} int main(void)
{
int T ;cin>>T;
while(T--)
{
int n; scanf("%d",&n);
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++) soda[i].id=i;
for(int i=;i<=n;i++) scanf("%d",&soda[i].l);
for(int i=;i<=n;i++) scanf("%d",&soda[i].r);
sort(soda+,soda++n,cmp);
int cnt=,pos=;
ans.clear();
while(!q.empty()) q.pop();
while(soda[pos].l==)
{
q.push(soda[pos]);
pos++;
if(pos>n) break;
}
while(!q.empty())
{
node tem=q.top(); q.pop();
if(tem.r<cnt) continue;
cnt++;
vis[tem.id]=;
ans.push_back(tem.id);
while(soda[pos].l==cnt)
{
q.push(soda[pos]);
pos++;
if(pos>n) break;
}
}
printf("%d\n",ans.size());
for(int i=;i<ans.size();i++) printf("%d ",ans[i]);
for(int i=;i<=n;i++) if(!vis[i]) printf("%d ",i);
printf("\n");
}
return ;
}
Aguin
1009 In Touch
1010 Just A String
1011 Key Set
组合数性质。
加和为2^n。奇偶和相等。
# include <iostream>
# include <cstdio>
using namespace std;
typedef long long LL;
const LL mod=; LL Pow(LL m,LL n)
{
LL b=;
while(n>)
{
if(n&) b=(b*m)%mod;
n=n>>;
m=(m*m)%mod;
}
return b;
} int main(void)
{
int T ;cin>>T;
while(T--)
{
LL n; scanf("%I64d",&n);
n--;
LL ans=Pow(,n)-;
printf("%I64d\n",ans);
}
return ;
}
Aguin