12.18
CF GlobalRound 6
可惜Efst了，不然估计能直接上紫。
A.Competitive Programmer
题意：给一个数，问是否存在其一个排列，使得是60的倍数？
思路：60倍数--含0且为6的倍数--含一个0且数位和为3且是2的倍数--含1个0且数位和为3且又含一个02468
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+20;
char s[M];
int main(){
int n;
scanf("%d",&n);
for(int z=1;z<=n;++z){
scanf("%s",s);
int len=strlen(s),sum=0;
int vou=0,v0=0;
for(int i=0;i<len;++i){
if (s[i]=='0')
++v0;
else if ((s[i]-'0')%2==0)
++vou;
sum+=s[i]-'0';
}
if (((v0>=2)||(v0&&vou))&&sum%3==0)
printf("red
");
else
printf("cyan
");
}
return 0;
}
B.Dice Tower
题意：一堆骰子可以堆在地面上，露出来的部分是四周和最上面那一个。现在给定一个数，问是否存在一种堆骰子的方法，使得露出来的部分的和等于这个数？
题解：除了最上面的，每个骰子均贡献14。而最上面的数可能是123456。因此n%14=1-6均可。但要特判1-6是不行的。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
int n;
scanf("%d",&n);
for(int z=1;z<=n;++z){
LL c;
scanf("%I64d",&c);
if ((c/14)&&(1<=c%14&&c%14<=6))
printf("YES
");
else
printf("NO
");
}
return 0;
}
C.Diverse Matrix
题意：给一个r*c的矩阵，对应的b数组为各行+各列的数的gcd。一个矩阵是diverse的，即b数组各数均不相同。一个矩阵的magnitude=b数组中的最大值，问给定r和c，构造一个magnitude最小的矩阵，并输出。
思路：最小的情况是b数组恰好为1-r+c这些数，则magnitude为r+c，这是最小的情况。下面思考怎么去构造这个矩阵。有一个易于理解的性质，即对于任一k>=1，有gcd(k,k+1)=1。因此我们指定A[i][j]=R[i]C[i]，其中R={1,2,3,……,r},C={r+1,r+2,……,r+c}即可满足条件。因为每一列都是对应的b数组中的值乘一堆连续的数，其gcd必然等于对应的b数组中的值，则满足题意。
需要注意r=1或者c=1的情况，此时必须是宽度为1的那个数的关键值为1，不然会出错。
即1*4的矩阵必须是2 3 4 5，不能是5 10 15 20。
#include<bits/stdc++.h>
using namespace std;
const int M=600;
int a[M][M],R[M],C[M];
int main(){
int r,c;
scanf("%d%d",&r,&c);
if (r==1&&c==1){
printf("0
");
return 0;
}
int cnt=0;
if (r<c){
for(int i=1;i<=r;++i)
R[i]=++cnt;
for(int i=1;i<=c;++i)
C[i]=++cnt;
}
else{
for(int i=1;i<=c;++i)
C[i]=++cnt;
for(int i=1;i<=r;++i)
R[i]=++cnt;
}
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
a[i][j]=R[i]*C[j];
for(int i=1;i<=r;++i){
for(int j=1;j<=c-1;++j)
printf("%d ",a[i][j]);
printf("%d
",a[i][c]);
}
return 0;
}
D.Decreasing Debts
题意：有n个人，互相欠债，问可否优化，使得债务总和最小，不需要保证债务牵扯的人最少。输出优化后的债务关系。
思路：这个题其实很思博……直接计算出每个人的净收益，这种情况下就是债务总和最小（绝对值和/2），之后随便连边就行了，每次保证耗尽一个关系即可。
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+20;
struct E{
int u,v,w;
E(int a=0,int b=0,int c=0):u(a),v(b),w(c){}
};
queue<int> upd;
queue<int> pnt[M][2];
vector<E> edge;
int vis[M];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v,d;
scanf("%d%d%d",&u,&v,&d),edge.push_back(E(u,v,d));
pnt[u][0].push_back(edge.size()-1),pnt[v][1].push_back(edge.size()-1);
}
for(int i=1;i<=n;++i)
vis[i]=1,upd.push(i);
while(!upd.empty())
if (!pnt[i][0].empty()&&!pnt[i][1].empty()){
while(!pnt[i][0].empty()&&edge[pnt[i][0].front().w==0])
pnt[i][0].pop();
}
return 0;
}
E. Spaceship Solitaire
题意：n种资源，每种资源均至少(a_i)时获胜。每天只能生产一种资源的一个单位。但有一些奖励，每个奖励都是t,s,u，即拥有了(t_j)但在的(s_j)资源时，即可获得一单位(u_j)资源。现每次修改一个奖励或者删除/增加一个奖励，每次输出最少几回合胜利。
题解：fst了。我的思路是，每一个bonus一定都用得上，所以只需要记录一下除了所有bonus之外，还需要加多少个资源。回头再补了。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r)>>1)
const int M=2e5+20,P=1e9+7;
struct Task{
int n,a[M*2],q;
map<int,int> mp[M];
LL ans=0;
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),ans+=a[i];
scanf("%d",&q);
}
void run(){
init();
for(int i=1;i<=q;++i){
int s,t,u;
scanf("%d%d%d",&s,&t,&u);
int ca=mp[s][t];
if (ca){
++a[ca];
if (a[ca]>=1)
++ans;
}
mp[s][t]=u;
if (u){
--a[u];
if (a[u]>=0)
--ans;
}
printf("%lld
",ans);
}
}
}t;
int main(){
t.run();
return 0;
}