A
可以暴力枚举；或者分析一下，把 A 中最大的当作队长，B 中最小的当作队长判断是否可行。
int a[10], b[10], s1 = 0, s2 = 0;
for(int i = 1; i <= 5; i++) cin >> a[i], s1 += a[i];
for(int i = 1; i <= 5; i++) cin >> b[i], s2 += b[i];
s1 += a[1], s2 += b[5];
if(s1 > s2) cout << "YES\n";
else cout << "NO\n";
B
的情况，输出
。
- 对于剩下的情况，设
的非零数个数是
，等于
的数个数是
，那么答案是
。注意约分。
- 约分不用 __gcd 也很简单，因为真分数里只有
需要约分。
void solve(){
cin >> a >> b >> c >> d >> e >> f;
int sk = 0, sn = 0;
if(a == 0 && b == 0 && c == 0 && d == 0 && e == 0) cout << "1/1000" << endl;
else{
if(a == f) sk++;
if(b == f) sk++;
if(c == f) sk++;
if(d == f) sk++;
if(e == f) sk++;
if(a != 0) sn++;
if(b != 0) sn++;
if(c != 0) sn++;
if(d != 0) sn++;
if(e != 0) sn++;
if(sk == 0) sn = 1;
if(sk == sn) sk = sn = 1;
if(sk == 2 && sn == 4) sk = 1, sn = 2;
cout << sk << "/" << sn << endl;
}
}
C
假设有 个人。那么输出 Other 的情况分为以下两种：
- 有
，其余人都回答了
。
- 这说明此时恰好有一种颜色的帽子是最多的，而且它在场上有
- 这说明此时恰好有一种颜色的帽子是最多的，而且它在场上有
- 所有人的答案都是相同的数
。
- 此时至少有两种颜色的帽子是最多的，而且它们在场上均恰好有
- 所以在以上条件基础上，还需要保证
才是合理的情况。
- 此时至少有两种颜色的帽子是最多的，而且它们在场上均恰好有
请注意所有人回答 的情况是有可能的，一定要放到第一类去判断（此时
应当成立）。
对于其它情况，答案都是 Lie。
int t, n, a[200010], c, pd, num, k;
int solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
if(a[1] == a[n] - 1){
num = 0, k = a[n];
for(int i = 1; i <= n; i++)
if(a[1] == a[i]) num++;
if(k == num) return 1;
else return 0;
}
else if(a[1] == a[n]){
if(a[1] == n - 1 || a[1] <= n / 2) return 1;
return 0;
}
else return 0;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> t;
while(t--) cout << (solve() ? "Other\n" : "Lie\n");
return 0;
}
D
BFS，一开始把所有叶子存入队列，每次向内延伸。对于每个节点记录下延伸的轮数（它等于最近叶子节点的距离）
最终找出记录值最远的一些点即可。
const int N = 200010;
int t, n, a[N], vis[N], d[N], sum, mx, res[N];
queue <pair<int, int> > q;
vector <int> e[N];
void solve(){
cin >> n;
for(int i = 1; i <= n; i++){
vis[i] = res[i] = d[i] = 0;
e[i].clear();
}
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
d[u]++, d[v]++;
}
for(int i = 1; i <= n; i++)
if(d[i] == 1){
q.push(mp(i, 0));
vis[i] = 1;
}
while(!q.empty()){
int x = q.front().first, v = q.front().second;
q.pop();
for(int y : e[x]){
if(vis[y]) continue;
vis[y] = 1;
res[y] = v + 1;
q.push(mp(y, v + 1));
}
}
sum = mx = 0;
for(int i = 1; i <= n; i++){
if(res[i] > mx)
mx = res[i], sum = 1;
else if(res[i] == mx)
sum++;
}
cout << sum << endl;
for(int i = 1; i <= n; i++)
if(res[i] == mx)
cout << i << " ";
cout << endl;
}
E
先只考虑子序列后一个是前一个数的倍数情况
考虑 DP。假设 表示扫描到位置
之前，最长符合条件的子序列的长度。
那么对于每个位置，有 。这里
表示
是
的约数。
但是这样做是 的，会超时，我们可以重新定义函数
。假设
表示，从左到右扫描到当前位置
时，选取的子序列最后一个数是
的最长子序列的长度。
然后对于当前的数 ，有
。由于一个数的约数个数最多是
级别的，所以对于每一个位置时间复杂度是
，总时间复杂度
。
再加上子序列后一个是前一个数的约数情况
该怎么往前找自己的倍数呢？如果逐个枚举，那么在 较小的时候枚举量会过大，导致 TLE。
那我们就应该提前为后面可能出现的数字进行铺垫。对于 ，若
是
的约数，那么
是
的倍数，我们在算完第
个位置的答案时，直接把这个答案下放到所有
约数对应的
值里，预判下一个数。
当然为了防止新下放的答案和原有的数字发生冲突，我们重新定义一个函数 专门储存这种下放情况的答案。
简单来说，对于每个新扫描到的位置 ，我们按顺序执行如下操作：
；
。
即先算一遍 再算一遍
。最后在所有
里找到最大的一个即可。时间复杂度
。std 预处理了值域内的所有约数，但是不写这个应该也能轻松通过。
const int N = 200010;
int n, a[N], f[N], g[N], t, ans;
vector <int> d[N];
void init(){
for(int i = 1; i < N; i++)
for(int j = i; j < N; j += i)
d[j].push_back(i);
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
ans = 0;
for(int i = 1; i <= n; i++)
f[i] = g[i] = 0;
for(int i = 1, mx; i <= n; i++){
mx = 0;
for(int j : d[a[i]])
mx = max(mx, f[j] + 1);
f[a[i]] = max(g[a[i]], mx);
for(int j : d[a[i]])
g[j] = max(g[j], f[a[i]] + 1);
}
for(int i = 1; i <= n; i++)
ans = max(ans, f[i]);
cout << ans << endl;
}
F
我们需要知道一个结论：
- 对于一个极长连续
o段，我们想通过修改 - 证明：
- 假设切出的两个连续
o段，长度均为。
- 那么两种情况的分数分别为
和
，显然前者更小。
- 相似的情况同样可以计算得知，长度尽量靠近时分数更小，这里就不写了。
- 假设切出的两个连续
- 所以我们可以定义一个函数
表示把一个长度为
的连续
o段修改处得到的最小分数。
- 定义
，即一个长度为
的连续
o段的分数。 - 那么
处切成
段，且尽可能切得均匀。
- 设
。三个量
分别代表切割出的最小段的长度、切出长度为
的段数量、切出长度为
- 那么
。
- 定义
对于一般的情况，我们会出现多个连续 o 段。
我们可以设计一个贪心的策略，希望每多切一刀，答案就会减少得尽可能多。那我们要怎么切呢？
一个很常见的误区就是每次选一段，切成均等的两半。这是不对的，原因可以看上面的结论。假设你可以切两刀，最优的分割方案是三等分，而不是对半后再在某一段对半。
所以对于初始情况的每个极长连续 o 段，我们假设记录它初始长度 ，当前已经被切的次数
。那么对于这被切了
次的段，多给你一次切一刀的机会，带来的减少量是
。这是一个反悔贪心式的操作，将补偿量作为更换方案的指标。
如果让你选择多个原始连续段的其中一个切，你需要挑出减少量最大的一个原始段。切完以后，把当前的减少量更新为 ，然后在这些原始段内重新选减少量最大的段，进行下一次切割。
这可以用堆维护。可以分析得知时间复杂度低于 ，可以轻松通过。
#define int long long
const int N = 1000010;
struct Cut{
int id, now, val;
}cut[N];
bool operator < (Cut x, Cut y){
return x.val < y.val;
}
int n, k, T, segs, a[N], state, sum;
char s[N];
priority_queue <Cut> q;
int S(int x){
return x * (x + 1) / 2;
}
int F(int i, int j){
if(i <= j) return 0;
int k = (i - j) / (j + 1);
int r = (i - j) - (j + 1) * k;
int p = (j + 1) - r;
return p * S(k) + r * S(k + 1);
}
int solve(){
int Sum = 0;
while(!q.empty()) q.pop();
for(int i = 1; i <= segs; i++){
Sum += S(a[i]);
q.push((Cut){i, 0, F(a[i], 0) - F(a[i], 1)});
}
for(int i = 1; i <= k && !q.empty(); i++){
int id = q.top().id, now = q.top().now, val = q.top().val;
q.pop();
Sum -= val;
if(now < a[id]) q.push((Cut){id, now + 1, F(a[id], now + 1) - F(a[id], now + 2)});
}
return Sum;
}
void Main(){
cin >> n >> k >> s;
segs = state = sum = 0;
for(int i = 0; i < n; i++){
if(s[i] == 'o'){
sum++;
if(!state) state = 1, a[++segs] = 1;
else a[segs]++;
}
else state = 0;
}
cout << solve() << endl;
}
全部评论
(2) 回帖