Codeforces Global Round 6
Codeforces Global Round 6
A. Competitive Programmer
1）题目大意：
给一串数字，请将他们重新排列产生一个可以有前导零的数字。问有没有可能排列出一个60的倍数，有可能输出red。
2）思路：
太久没打了这题目一上来我居然写了个搜索
60可以分成3，2，10。也就是说必须有0，必须是3和2的倍数。
在该数是3的倍数的情况下，要么有至少一个偶数和至少一个0，要么至少有两个0 。
3）代码：
string s ;
void solve(){
cin >> s ;
ll nume = 0 , num0 = 0 ;
ll sum = 0 ;
for(char c : s){
sum += c - '0' ;
if(c == '0') num0 ++ ;
if((c - '0') % 2 == 0) nume ++ ;
}
if(sum % 3 == 0 && (num0 >= 1 && nume >= 2 || num0 >= 2)) cout << "red\n" ;
else cout << "cyan\n" ;
}
4）扩展：
倍数的性质，这题是60 。那么可以思考一下其他数字的倍数的性质
B. Dice Tower
1）题目大意：
有无穷个骰子，将他们垒起来，最底层和接触面的点数不算，算表面数字和。给若干个数字，问该数字有没有可能出现。
2）思路：
骰子的特点是对面两个点数和是7 。就是说每一层侧面点数和是2*7 。那么将所给数字模上14就能得出最顶层的数字了。若该数字是1~6中的一个那就ok 。当然，要注意题中会给小于十五的数字，这连一颗骰子都没有，需要特判。
3）代码：
void solve(){
ll x ;
cin >> x ;
if(x % 14 >= 1 && x % 14 <= 6 && x >= 15) cout << "YES\n" ;
else cout << "NO\n" ;
}
C. Diverse Matrix
1）题目大意：
给出一个r*c的矩阵，将该矩阵的每一列每一行的最大公约数求出放到一个长度为r+c的数组中，每一个最大公约数不相同，需要使得所有gcd的最大值最小。
2）思路：
真的是无语，为什么一个数会有gcd啊...
行gcd从1到r，列gcd从r+1到r+c构造就行 。特判一下一列的情况。
3）代码：
void solve(){
cin >> n >> m ;
if(n == 1 && m == 1) {
cout << 0 ; return ;
}
if(m == 1){
for(int i = 1 ; i <= n ; i ++ )
cout << i + 1 << "\n" ;
return ;
}
for(int i = 1 ; i <= n ; i ++ )
for(int j = n + 1 ; j <= n + m ; j ++ )a[i][j - n] = i * j ;
for(int i = 1 ; i <= n ; i ++ , cout << "\n")
for(int j = 1 ; j <= m ; j ++ ) cout << a[i][j] << " " ;
}
D. Decreasing Debts
1）题目大意：
有m条借钱关系，（u,v,w）表示v借给uw元钱。现在需要我们简化这些关系使得总流水最小（总流水就是所有借钱关系的金额和）
2）思路：
我一开始真的以为是图论题目，以为有什么奇怪的算法可以解这个。结果一看题解，人麻了。要点就是收支平衡。把每个人的钱数量算好，然后排个序，欠钱最多的人还钱给借出最多的人，用双指针做一下。
3）代码：
ll n , m , num ;
struct prsn {
ll w , idx ;
}a[N] ;
struct{
ll u , v , w ;
}ans[N] ;
bool cmp(prsn u , prsn v){
return u.w < v.w ;
}
void solve(){
cin >> n >> m ;
for(int i = 1 ; i <= m ; i ++ ){//算好每个人的钱，负数表示欠钱
ll u , v , money ;
cin >> u >> v >> money ;
if(u == v) continue ;
a[u].w -= money ;
a[v].w += money ;
}
for(int i = 1 ; i <= n ; i ++ )a[i].idx = i ;
//debug ;
sort(a + 1 , a + n + 1 , cmp) ;
ll i = 1 , j = n ;
while(i < j){
while(i < j && a[i].w == 0) i ++ ;
while(i < j && a[j].w == 0) j -- ;//找到第一个有欠钱关系的负债人和债主
if(i >= j) break ;
ll d = min(abs(a[i].w) , a[j].w) ;
a[i].w += d ;
a[j].w -= d ;
ans[++ num].u = a[i].idx ;
ans[num].v = a[j].idx ;
ans[num].w = d ;
}
cout << num << "\n" ;
for(int i = 1 ; i <= num ; i ++ )
cout << ans[i].u << " " << ans[i].v << " " << ans[i].w << "\n" ;
}
E. Spaceship Solitaire
1）题目大意：
有n个东西，做一个需要一次操作。需要做完goal[i]个东西才算完成任务。现在给m个成就（u,v,w）表示做了v个u就能免费获得一个w。问在有1~i个成就的时候完成任务分别需要最少几次操作。
2）思路：
说实话这题不太明白。但是这和dp有点相似。我们要算第i次的最优，那就是从i-1转移过来的。而且这道题需要倒过来思考。我们需要完成i属于1到n的每一个goal[i]，就是说在一个成就都没有的时候我们需要ans = sum（goal[i]）次操作。那如果有了一个成就送我们一个x物品，那我们x物品就可以少做一个，操作数就少一次。当然，如果我们已经完成了goal[x]他再送，我们可以拿，但是不影响操作数。这题比较抽象，很有意思
3）代码：
ll n , m , ans ;
ll goal[N] , rwd[N] ;//reward
map > mp ;
void solve(){
cin >> n ;
get1(goal , n) ;
for(int i = 1 ; i <= n ; i ++ ) ans += goal[i] ;
cin >> m ;
while(m -- ){
ll u , v , w ;
cin >> u >> v >> w ;
if(!mp[u][v]){//若该成就没有出现过
mp[u][v] = w ;
rwd[w] ++ ;
if(rwd[w] <= goal[w]){
//该任务奖励有用
ans -- ;//就可以少做一次该任务奖励
}
}else{//已经出现过该任务
rwd[mp[u][v]] -- ;
if(rwd[mp[u][v]] < goal[mp[u][v]]) ans ++ ;
mp[u][v] = w ;//任务顶掉
rwd[w] ++ ;
if(rwd[w] <= goal[w]){
ans -- ;
}
}
cout << ans << "\n" ;
}
}
4）拓展：
这种多状态输出的题目很大概率是每阶段最优一点一点转移过来的。和dp很像。
一些唠叨：
ACMer生涯过去了一年多，大学生活过去 了一年多，这一年里我很迷茫。时间像火车一样毫不留情地走着，而我就像穿着尿布的婴儿在月台上，在茫茫人海里呆呆地站着。我不知道要去哪里，我不知道要去找谁。值得庆幸的是，我是一个幸运的傻瓜，我遇到了一起打acm的伙伴们，我遇到了朱老师，遇到了阿伟老师。他们帮我拨开了遮盖天空的云雾，让我看到我想去的地方，让我知道我需要做什么，更重要的是，让我想要去做什么。真的无比感谢...