CF EDU 5

A. Comparing Two Long Integers

思路

类似于高精的比较， 放到字符串中， 先比较位数， 在从高位向地位比较即可。
注意先去掉前导0

代码

#includeusing namespace std;string a;
string b;
int main()
{getline(cin, a);getline(cin, b);//bool flag = false;int cnta = 0, cntb = 0;if(a[0] == '0'){int now = 0;while(a[now] == '0'){now++;}cnta = now;//	break;}if(b[0] == '0'){int now = 0;while(b[now] == '0'){now++;}cntb = now;//	break;}//cout << cnta << " " << cntb << endl;int lena = a.size() - cnta + 1;int lenb = b.size() - cntb + 1;if(lena != lenb){if(lena > lenb){printf("%c", '>');}else{printf("%c", '<');}return 0;}for(int i = 1; i <= lena; i++){if(a[cnta] < b[cntb]){printf("%c", '<');return 0;}else if(a[cnta] > b[cntb]){printf("%c", '>');return 0;}cnta++;cntb++;}printf("%c", '=');return 0;
}

大佬直接用两个字符串比较， 大佬用的string函数， 这种函数有两个参数（a, b), 就是把大小为a的字符串全部置成b这个字符， 那么大佬就是用这个函数将两串变成有着同样个数的前导0， 再进行比较。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;string a, b;int main()
{cin >> a >> b;if (a.size() < b.size()) a = string(b.size() - a.size(), '0') + a;else if (a.size() > b.size()) b = string(a.size() - b.size(), '0') + b;if (a < b) printf("<\n");else if (a > b) printf(">\n");else printf("=\n");return 0;
}

B. Dinner with Emma

思路

按照提议模拟即可， 找每行最小值的最大值

代码

#includeusing namespace std;int n, m;
int ans; 
int c[110][110];
int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){int minn = 1000000000;for(int j = 1; j <= m; j++){cin >> c[i][j];minn = min(c[i][j], minn);}ans = max(ans, minn);}cout << ans << endl;return 0;
}

C. The Labyrinth

思路

显然用搜索。爆搜每个‘*’很容易TLE， 我们考虑预处理联通快。
对于每一个’ * ’， 与他相连的所有的‘.'的联通快的大小， 因为又要把他变为空格子， 所以再加上1， 就是当这个impassable cell变成empty cell时可以形成的空的blocks的格子数。
注意， 如果他的上下左右都是相同的联通快的话， 只记一次

代码

#includeusing namespace std;char mp[1000010];
int n, m;
bool vis[1000010]; 
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
int block[1000010];
int size[1000010];
int cnt;
int ans[1010][1010];
bool judge(int x, int y)
{if(x < 1 || x > n || y < 1 || y > m){return 1;}return 0;
}
void dfs(int x, int y)
{int v = (x-1) * m + y;vis[v] = 1;block[v] = cnt;size[cnt]++;//cout << x << " " << y << endl;for(int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];int nv = (nx-1) * m + ny;if(judge(nx, ny)){continue;}if(mp[nv] == '.' && !vis[nv]){dfs(nx, ny);}}
}
void print()
{for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(mp[(i-1) * m + j] == '.'){printf("%c", '.');}else{printf("%d", ans[i][j]);}}printf("\n");}
}
int main()
{scanf("%d %d", &n, &m);getchar();for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){mp[(i-1) * m + j] = getchar();}getchar();}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(mp[(i-1) * m + j]  == '.' && !vis[(i-1) * m + j]){cnt++;dfs(i, j);//	printf("%d:\n", cnt);}}}//cout << cnt << endl;/*for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){int v = (i-1) * m + j;cout << mp[v];}cout << endl;}cout << mp[2] << endl;*/for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){int v = (i-1) * m + j;if(mp[v] == '*'){ //cout << i << " " << j << endl;ans[i][j] = 1;set<int> st;//memset(vis, 0, sizeof(vis));for(int k = 0; k < 4; k++){int nx = i + dx[k];int ny = j + dy[k];int nv = (nx-1) * m + ny;/*	if(i == 2 && j == 5){cout << nx << " " << ny << endl;}*/if(judge(nx, ny)){continue;}if(mp[nv] == '.'){st.insert(block[nv]);}}for(set<int>::iterator it = st.begin(); it != st.end(); it++){ans[i][j] += size[*it];ans[i][j] %= 10;}}}}print();return 0;
}

大佬用的vector再加去重， 我是直接用的set， 还有我用的一维标网格， 而大佬用的二维

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;const int Maxn = 1005;
const int Maxd = 4;
const int dy[Maxd] = {-1, 0, 0, 1};
const int dx[Maxd] = {0, -1, 1, 0};int n, m;
char B[Maxn][Maxn];
int cur, col[Maxn][Maxn];
int siz[Maxn * Maxn];
char R[Maxn][Maxn];int getSiz(int r, int c, int mycol)
{if (r < 0 || r >= n || c < 0 || c >= m || B[r][c] == '*' || col[r][c] > 0) return 0;col[r][c] = mycol; int res = 1;for (int i = 0; i < Maxd; i++)res += getSiz(r + dy[i], c + dx[i], mycol);return res;
}int main()
{scanf("%d %d", &n, &m);for (int i = 0; i < n; i++)scanf("%s", B[i]);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (B[i][j] == '.' && col[i][j] <= 0) {cur++;siz[cur] = getSiz(i, j, cur);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)if (B[i][j] == '.') R[i][j] = '.';else {vector <int> seq;for (int d = 0; d < Maxd; d++) {int r = i + dy[d], c = j + dx[d];if (0 <= r && r < n && 0 <= c && c < m)seq.push_back(col[r][c]);}sort(seq.begin(), seq.end()); seq.erase(unique(seq.begin(), seq.end()), seq.end());int res = 1;for (int d = 0; d < seq.size(); d++)res = (res + siz[seq[d]]) % 10;R[i][j] = '0' + res;}R[i][m] = '\0';printf("%s\n", R[i]);}return 0;
}

D Longest k-Good Segment

思路

可以用尺取法， 具体来说， 对于每一个左端点， 看他在合法的情况下最长能延伸到的长度。
用一个桶来记录每个字符出现的次数。

代码

#includeusing namespace std;int n, k;
int a[500010];
int cnt[1000010]; 
int ansl, ansr;
int main()
{cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];}int l = 1, r = 1;int num = 1;int len = 0;cnt[a[l]]++;while(r <= n){while(num <= k && r <= n){r++;if(!cnt[a[r]]){num++;}cnt[a[r]]++;}//r--;if(r - l > ansr - ansl){//cout << l << " " << r << endl;ansl = l;ansr = r-1;}cnt[a[l]]--;if(!cnt[a[l]]){num--;}l++;}cout << ansl << " " << ansr << endl;return 0;
}

E Sum of Remainders

思路

标准的余数求和；
可以参考这里。
整数分块。
每块有n /(n / i);
原式 = n × m − ∑ i = 1 m ⌊ i n ⌋ × n n \times m - \sum_{i = 1}^m \lfloor \frac{i}{n} \rfloor \times n n×m−∑i=1m​⌊ni​⌋×n
对于每一块，用等差数列求和公式即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！