【cf比赛记录】Codeforces Round #601 (Div. 2)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Codeforces Round #601 (Div. 2) ---- 比赛传送门

周二晚因为身体不适鸽了，补题补题

// http://codeforces.com/contest/1255/problem/A /* 签到题简单的贪心题本考虑过是否有先小于再加上去会更小的情况但两种情况恰好步数是一样的 */ #include<iostream> #include<cstdio> #include<cmath> using namespace std;int T; int a, b; int num[] = { 5, 2, 1 };int main() { scanf("%d", &T); while(T--){ scanf("%d %d", &a, &b); int ans = 0, tmp, i = 0; if(a != b){ tmp = abs(a - b); while(tmp){ int div = tmp / num[i]; ans += div; tmp -= num[i] * div; i++; } } printf("%d\n", ans); } return 0; }

// http://codeforces.com/contest/1255/problem/B /* 图形... 既然 m <= n 的话，要满足题目的要求就只能 m == n 了那既然如此......把冰箱都连成环就 Ok 了 */ #include<iostream> #include<cstdio> #include<algorithm> using namespace std;int T, n, m;int main() { scanf("%d", &T); while(T--){ scanf("%d %d", &n, &m); int a, tot = 0; for(int i = 1; i <= n; i++){ scanf("%d", &a); tot += a; } if(n < 3 || m != n) printf("-1\n"); // 特判：当出现这种情况时，是肯定不符合的 else { printf("%d\n", tot * 2); for(int i = 1; i <= n; i++){ printf("%d %d\n", i, i % n + 1); } } } return 0; }

// http://codeforces.com/contest/1255/problem/C /* 找规律 ---- 拓扑排序首尾的数是最好找的，因为只会出现一次根据样例分析 5 4 3 2 2 3 5 4 1 2 依次出现的次数 1:1 2:3 3:2 4:2 5:1 可见， 1, 5各只出现了 1 次因此首尾分别是 1 5，然后 2 出现了 3 次所以 2 是中间数然后 3 4 就可以根据 1 2 的收尾排序就可以确认了 1 4 2 3 5 或者 5 3 2 4 1因此，每次找 tot[] 为 1 的数加进首跟尾要提前记录每个点所在的 arr 位置（减少查找时的时间） ----拓扑排序但由于自己实现太繁琐，所以没实现出来就去找AC的代码，发现了dalao的凝练版 ----参考了 yongwhan dalao的代码，#65412415 */#include<iostream> #include<cstdio> #include<vector> using namespace std;int n; int a, b, c; int tot[100005]; bool used[100005]; vector<int> num[100005]; /* 对该代码的分析：因为每组只有3个数所以对于样例 1 4 2 3 5 这组数据 1 的相邻有 4 2 4 的相邻有 1 2 3 2 的相邻有 1 4 3 5 ... 先找出 1 (这个很好找) 找出 1 后可以确立第二个数是 4 (因为 4 只出现了两次，而 2 出现了 3 次) 然后从 1 开始找 "下一个数", 此时与 1 相邻的只有 2 了 ---- 输出，并记录其已被使用接着从 4 开始找还未被使用过且相邻的数，于是进而找到 3 接着从 2 开始找，接着就找到了 5 即便 n > 5 这样的方法也是成立的，如 n = 7; 排序是 3 2 1 7 6 5 4 先找到 3 2 然后从 3 开始找，相邻的还没用的就只剩下 1 接着从 2 开始找，同理还剩下 7 继续从 1 开始找，同理还剩下 6 继续从 7 开始找，剩下 5 最后从 6 开始找，最后的是 4 ... 所以dalao的代码还是tql */ int main() { scanf("%d", &n); for(int i = 0; i < n - 2; i++){ scanf("%d %d %d", &a, &b, &c); num[a].push_back(b); num[a].push_back(c); num[b].push_back(a); num[b].push_back(c); num[c].push_back(a); num[c].push_back(b); tot[a]++; tot[b]++; tot[c]++; } int x, y, z; for(int i = 1; i <= n; i++){ if(tot[i] == 1){ x = i; break; } } if(tot[num[x][0]] == 2) y = num[x][0]; else y = num[x][1]; used[x] = used[y] = true; printf("%d %d ", x, y); // 以下的注释可以去掉输出看看更方便理解... for(int i = 1; i <= n - 2; i++){ // printf("\nx:%d\n", x); for(int j = 0; j < num[x].size(); j++){ // 找到相邻且未被使用过的点 // printf("j:%d num[x][]:%d used:%d\n", j, num[x][j], used[num[x][j]]); if(!used[num[x][j]]) { // 由于特殊性，这个点只有 1 个 z = num[x][j]; // printf("z:%d\n", z); // 从这里看出，每次这么进行的时候 z 只改变了一次 } } used[z] = true; printf("%d ", z); x = y; y = z; } return 0; }// 下面是我自己敲的臃肿代码思想是运用拓扑排序加优化结果把自己绕晕了 //#include<iostream> //#include<cstdio> //#include<stack> //#include<vector> //#include<algorithm> //#include<queue> //#include<stack> //using namespace std; // //int n; //struct jilu{ // int tot, who; //}cot[100005]; // tot 记录 who 出现了多少次; //struct node{ // int a, b, c; //}arr[100005]; //bool used[100005]; // 记录哪个arr已经被用过 //vector<int> tmp[100005]; // 记录数字 i 所在输入数组里的位置 //queue<int> take; // 本次进行了减减的数 //stack<int> ans2; //queue<int> ans1; // //bool cmp(jilu a, jilu b){ // if(a.tot == b.tot) return a.who < b.who; // return a.tot < b.tot; //} // // //int main() //{ // scanf("%d", &n); // for(int i = 1; i <= n - 2; i++){ // scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c); // cot[arr[i].a].tot++; cot[arr[i].b].tot++; cot[arr[i].c].tot++; // cot[arr[i].a].who = arr[i].a; // cot[arr[i].b].who = arr[i].b; // cot[arr[i].c].who = arr[i].c; // tmp[arr[i].a].push_back(i); // tmp[arr[i].b].push_back(i); // tmp[arr[i].c].push_back(i); // } // // sort(cot + 1, cot + n + 1, cmp); // // ans1.push(cot[1].who); ans2.push(cot[2].who); // for(int i = 0; i < tmp[cot[1].who].size(); i++){ // 首的初始化 // cot[cot[1].who].tot--; // int p = tmp[cot[1].who][i]; // used[p] = true; // if(arr[p].a != cot[1].who) { // cot[arr[p].a].tot--; // take.push(arr[p].a); // } // if(arr[p].b != cot[1].who) { // cot[arr[p].b].tot--; // take.push(arr[p].b); // } // if(arr[p].c != cot[1].who) { // cot[arr[p].c].tot--; // take.push(arr[p].c); // } // } // // for(int i = 0; i < tmp[cot[2].who].size(); i++){ // 尾的初始化 // cot[cot[2].who].tot--; // int p = tmp[cot[2].who][i]; // used[p] = true; // if(arr[p].a != cot[2].who) { // cot[arr[p].a].tot--; // take.push(arr[p].a); // } // if(arr[p].b != cot[2].who) { // cot[arr[p].b].tot--; // take.push(arr[p].b); // } // if(arr[p].c != cot[2].who) { // cot[arr[p].c].tot--; // take.push(arr[p].c); // } // } // // while(!take.empty()){ // ... // } // // return 0; //}

// http://codeforces.com/contest/1255/problem/D // 参考：HazemAk1 的 #65396404 的 AC 代码 /* 要使 k 头奶牛在点上取得的 R 尽量均匀 ---- 即最大与最小的差 <= 1 要求每头牛所占的 R 的数目很简单关键是处理图的连块问题搜索*/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const char out[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; // 62种输出情况 int T, H, W, k, R, now; char maze[102][102]; char ans[102][102]; int have[70]; //bool used[102][102]; //struct node{ // int h, w; //}; //queue<node> q; //int dw[] = { 1, 0, -1, 0 }; //int dh[] = { 0, 1, 0, -1 };void solve(){ int x = 0, y = 0; for(int i = 0; i < k; i++){ while((have[i] || i == k - 1) && x < H){ // 当还没选够选够或者是最后一头牛的时候就继续进行， x 还没到达最大行的时候继续进行 ans[x][y] = out[i]; // 既然还没有找完那该点就是当前牛的位置啦 if(maze[x][y] == 'R') have[i]--; // 如果有一饭点就减减 if(x % 2 == 0){ // 当此时为偶数行的时候就从左往右遍历（因为是从0开始） y++; if(y > W - 1) x++, y = W - 1; // 下一行操作 } else { // 同理当此时为奇数行的时候就从右往左遍历 y--; if(y < 0) x++, y = 0; // 下一行操作 } } } }int main() { scanf("%d", &T); while(T--){ R = 0; // 记录总的R点数 memset(used, false, sizeof(used)); scanf("%d %d %d", &H, &W, &k); for(int i = 0; i < H; i++){ scanf("%s", maze[i]); for(int j = 0; j < W; j++){ if(maze[i][j] == 'R') R++; } } // 给每头牛所占有的R点个数赋值 int l = R / k; int lea = R - k * l; for(int i = 0; i < k; i++){ have[i] = l + (lea > 0); lea--; } solve(); // 输出 for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ printf("%c", ans[i][j]); } printf("\n"); }// 以下是我自己写的方法，繁杂，不利索 // now = 0; // for(int i = 0; i < H; i++){ // for(int j = 0; j < W; j++){ // if(!used[i][j]){ ////// printf("now:%d\n", now); //// used[i][j] = true; //// if(maze[i][j] == 'R') have[now]--; ////// printf("h:%d w:%d have:%d\n", i, j, have[now]); //// q.push({i, j}); //// bfs(); //// now++; // dfs(i, j, now, have[now]); // } // } // } } return 0; }//bfs 也绕晕了自己 //void bfs(){ // bool flag = false; // while(!q.empty()){ // node n = q.front(); q.pop(); // ans[n.h][n.w] = out[now]; // // for(int i = 0; i < 4; i++){ // int nh = n.h + dh[i]; int nw = n.w + dw[i]; // if(0 <= nh && nh < H && 0 <= nw && nw < W && !used[nh][nw] && (now == k - 1 || !flag)){ // used[nh][nw] = true; // q.push({nh, nw}); // if(maze[nh][nw] == 'R'){ //// printf("now:%d nh:%d nw:%d maze:%c\n", now, nh, nw, maze[nh][nw]); // have[now]--; // if(have[now] == 0 && now != k - 1){ // flag = true; // } // } // } // } // } //}// 我这个 dfs 有坑 //void dfs(int h, int w, int &now, int &tot){ // used[h][w] = true; // ans[h][w] = out[now]; // if(maze[h][w] == 'R'){ // tot--; // maze[h][w] = '.'; // if(tot == 0 && now != k - 1){ // now++; // return ; // } // } // // for(int i = 0; i < 4; i++){ // int nh = h + dh[i]; int nw = w + dw[i]; // if(0 <= nh && nh < H && 0 <= nw && nw < W && !used[nh][nw]){ // dfs(nh, nw, now, tot); // if(tot == 0) return ; // } // } //}