Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4) 题解 Happy Birthday, Polycarp! Make Them Odd As Simple as One and Two Let's Play the Words? Two Fairs Beautiful Rectangle
- Happy Birthday, Polycarp!
- Make Them Odd
- As Simple as One and Two
- Let's Play the Words?
- Two Fairs
- Beautiful Rectangle
[Time Limit: 1 squad Memory Limit: 256 MB
]
暴力枚举所有数字全为 (i、iin[1,9])，然后暴力判断有多个全为 (i) 的数在 (n) 以内即可。
view
#include <unordered_map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
ll n, m;
int cas, tol, T;
int main() {
scanf("%d", &T);
while(T--) {
ll ans = 0;
scanf("%lld", &n);
for(int i=1; i<=9; i++) {
ll tmp = i;
while(tmp <= n) {
ans++;
tmp = tmp*10+i;
}
}
printf("%lld
", ans);
}
return 0;
}
Make Them Odd
[Time Limit: 3 squad Memory Limit: 256 MB
]
把数一直除 (2)，记录除了多少次。
那么对于剩余的数相同的数，只要记录变成他需要被除的最大次数就即可。
最后的答案就是变成这些剩余数的所需次数的累和。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
map<int, int> mp;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
mp.clear();
ll ans = 0;
for(int i=1, x; i<=n; i++) {
scanf("%d", &x);
int res = 0;
while(x%2 == 0) {
res++;
x /= 2;
}
if(mp.count(x)) mp[x] = max(mp[x], res);
else mp[x] = res;
}
for(auto v : mp) ans += v.se;
printf("%lld
", ans);
}
return 0;
}
As Simple as One and Two
[Time Limit: 3 squad Memory Limit: 256 MB
]
首先考虑 (twone)，这里因为的 (o) 被 (one) 和 (two) 都用到了，所以直接删除它就可以了。
在考虑其他情况，对于 (one) 可能存在 (one、oneeee、oooone、oooneeee)，那么我们可以发现，删掉 (o) 或者删掉 (e) 都不是很好的选择，但是 (n) 确实不能重复出现的，所以只要删掉 (n) 就可以了。对于 (two) 也是一样的道理，删掉 (w) 是最好的。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
char s[maxn];
int main() {
scanf("%d", &T);
while(T--) {
vector<int> ans;
scanf("%s", s+1);
int len = strlen(s+1);
for(int i=1; i<=len; i++) {
if(i+2<=len && s[i]=='t' && s[i+1]=='w' && s[i+2]=='o') {
if(i+4<=len && s[i+3]=='n' && s[i+4]=='e') {
ans.pb(i+2);
i = i+4;
} else {
ans.pb(i+1);
i = i+2;
}
}
if(i+2<=len && s[i]=='o' && s[i+1]=='n' && s[i+2]=='e') {
ans.pb(i+1);
i = i+2;
}
}
printf("%d
", ans.size());
for(auto v : ans) printf("%d ", v);
printf("
");
}
return 0;
}
Let's Play the Words?
[Time Limit: 3 squad Memory Limit: 256 MB
]
把字符串分成四类，分别是 (0..0、1...1、0...1、1...0)。
首先可以发现，如果存在一个第 (3/4) 类的字符串，第 (1/2) 类的字符串都一定能够拼接起来，完全可以忽略掉。如果不存在第 (3/4) 类的字符串，那么 (1/2) 类的字符串只能独自出现，否则一定拼接不起来。
接下来考虑存在 (3/4) 类的字符串，第 (3) 类的字符串有 (n) 个，第 (4) 类的字符串有 (m) 个。
假设 (n>m)，那么我们只要暴力翻转第 (3) 类的字符串变成第 (4) 类的字符串，使得 (abs(n-m)<=1)，就一定可以拼接起来，对于 (m>n) 的情况也是类似，只要翻转第 (4) 类的字符串变成第 (3) 类的就可以。
为什么这么做可以呢？因为题目保证的一开始给出的字符串都是 (different) 的，那么我把第 (3) 类的字符串翻转过去，一定不会对其他第 (3) 类字符串是否需要翻转造成影响，那么我只要每次贪心翻转就够了。
view
#include <unordered_map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
unordered_map<string, bool> mp;
vector<pair<string, int> > vv[4];
int main() {
scanf("%d", &T);
while(T--) {
mp.clear();
for(int i=0; i<4; i++) vv[i].clear();
scanf("%d", &n);
string s;
for(int i=1; i<=n; i++) {
cin >> s;
if(s[0]=='0' && s[s.length()-1]=='0') vv[0].pb({s, i});
if(s[0]=='1' && s[s.length()-1]=='1') vv[1].pb({s, i});
if(s[0]=='0' && s[s.length()-1]=='1') vv[2].pb({s, i});
if(s[0]=='1' && s[s.length()-1]=='0') vv[3].pb({s, i});
}
if(vv[0].size() == n || vv[1].size() == n) {
printf("0
");
continue;
}
if(vv[0].size() && vv[1].size() && !vv[2].size() && !vv[3].size()) {
printf("-1
");
continue;
}
int id = 2;
if(vv[3].size() > vv[2].size()) id = 3;
n = vv[id].size(), m = vv[id^1].size();
vector<int> ans;
for(auto it : vv[id^1]) mp[it.fi] = true;
for(auto it : vv[id]) {
if(abs(n-m) <= 1) break;
string ss = it.fi;
reverse(ss.begin(), ss.end());
if(mp.count(ss)) continue;
ans.push_back(it.se);
n--, m++;
}
int sz = ans.size();
printf("%d
", sz);
if(sz==0) printf("
");
for(int i=0; i<sz; i++)
printf("%d%c", ans[i], i==sz-1 ? '
':' ');
}
return 0;
}
Two Fairs
[Time Limit: 3 squad Memory Limit: 256 MB
]
对于给出的开始和终止位置 (s、t)，我需要找到的是从 (s) 出发不经过 (t) 可以到达的节点数和从 (t) 出发不经过 (s) 可以到达的节点数。
对于找从 (s) 出发不经过 (t) 的节点，可以先 (dfs) 一边把从 (t) 出发可以到达的节点数标记起来，终止条件为遇到 (s) 节点或者无路可走。然后再从 (s) 出发看哪些节点是没有被标记过的。这样找出来的节点就一定是满足条件的，第二种同理。
最后的答案就是这两种节点数的乘积。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
int s, t;
vector<int> g[maxn];
bool vis[maxn];
void dfs1(int u, int res) {
if(vis[u]) return ;
if(u == res) return ;
vis[u] = 1;
for(auto v : g[u]) dfs1(v, res);
}
ll dfs(int u) {
if(vis[u]) return 0;
vis[u] = 1;
ll ans = 1;
for(auto v : g[u])
ans += dfs(v);
return ans;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i=1; i<=n; i++) g[i].clear();
for(int i=1, u, v; i<=m; i++) {
scanf("%d%d", &u, &v);
g[u].pb(v), g[v].pb(u);
}
ll ans1 = 0, ans2 = 0;
for(int i=1; i<=n; i++) vis[i] = 0;
dfs1(t, s);
// for(int i=1; i<=n; i++) printf("%d%c", vis[i], i==n?'
':' ');
ans1 = dfs(s)-1;
for(int i=1; i<=n; i++) vis[i] = 0;
dfs1(s, t);
// for(int i=1; i<=n; i++) printf("%d%c", vis[i], i==n?'
':' ');
ans2 = dfs(t)-1;
printf("%lld
", ans1*ans2);
}
return 0;
}
Beautiful Rectangle
[Time Limit: 1000 msquad Memory Limit: 256 MB
]
首先发现可以枚举最后矩形的高，如果能够想办法计算出在高固定的情况下，最大可以放的宽是多少。那么枚举所有的高，就可以得到最后应该构造的矩阵是什么样的。
假设高为 (h) 且小于宽 (w)，那么对于同样的数字，最多只能放 (h) 个。所以我们可以计算所有数字出现的次数，那么对于出现次数小于 (h) 的数字，可以都取，对于出现次数大于 (h) 的，只取其中的 (h) 个出来用。这样就得到了最多可以放的元素的个数，也就可以得到对应的 (w)。
那么构造的时候，我们只要把每个元素按 ((i,1)、(i+1, 2)、(i+2,3)) 这样斜着放下去就可以构造出矩阵。
但是我们还要防止一种情况的出现，也就是可用元素有 (a、b、b、c、c) 五个，而此时我需要四个，如果我从前往后希望先使用出现次数少的元素，我会拿到 (a、b、b、c) 四个，把原本后面的整体拆成前面就应该已经放完的类型，变成
[egin{matrix}
a & b\
c & b
end{matrix}
]
为了防止这种情况，我们可以从后往前取先使用出现次数多的元素来放，使用 (c、c、b、b) 放成
[egin{matrix}
c & b\
b & c
end{matrix}
]
这样就算拆开了某一部分，并不会改变这一部分原本应该放的顺序，就可以避免上面的情况。
view
/***************************************************************
> File Name : f.cpp
> Author : Jiaaaaaaaqi
> Created Time : Mon 16 Dec 2019 03:22:17 PM CST
***************************************************************/
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 4e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
struct Node {
int c, v;
bool operator < (Node a) const {
return c < a.c;
}
} node[maxn];
map<int, int> mp;
vector<int> g[maxn];
int main() {
freopen("in", "r", stdin);
scanf("%d", &n);
for(int i=1, x; i<=n; i++) {
scanf("%d", &x);
mp[x]++;
}
node[tol=0] = {0, 0};
for(auto it : mp) node[++tol] = {it.se, it.fi};
sort(node+1, node+1+tol);
int h = 0, w = 0, sum = 0;
for(int i=1, j=0; i*i<=n; i++) {
while(j<=tol && node[j].c<=i) sum += node[j++].c;
int use = sum + (tol-j+1)*i;
use /= i;
if(i > use) continue;
if(h*w < i*use) h = i, w = use;
}
for(int i=1; i<=h; i++) {
g[i].clear();
for(int j=0; j<=w; j++) {
g[i].pb(0);
}
}
vector<int> ans;
for(int i=1; i<=tol; i++) {
node[i].c = min(node[i].c, h);
while(node[i].c--) ans.pb(node[i].v);
}
int now = 0;
for(int j=1; j<=w; j++) {
int x = 1, y = j;
while(x <= h) {
g[x][y] = ans[now++];
x++, y = y%w+1;
}
}
printf("%d
", h*w);
printf("%d %d
", h, w);
for(int i=1; i<=h; i++) for(int j=1; j<=w; j++)
printf("%d%c", g[i][j], j==w?'
':' ');
return 0;
}