- Happy Birthday, Polycarp!
- Make Them Odd
- As Simple as One and Two
- Let's Play the Words?
- Two Fairs
- Beautiful Rectangle
Happy Birthday, Polycarp!
[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;
}