A. PENTA KILL!
题意：给定一个击杀序列，死亡不影响连杀，问是否有人完成五杀
分析：模拟，将每个选手的名字进行哈希，将属于每一个人的击杀序列处理出来，对每个人进行枚举判断即可
ac代码
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
using namespace std;
int n,m,k,t;
int cnt;
unordered_map<string,int> mp;
int get(string & s)
{
if(!mp[s]) mp[s] = ++ cnt;
return mp[s];
}
int main()
{
ios;
cin >> n;
vector<int> name[11];
while(n --)
{
string a,b;
cin >> a >> b;
int xa = get(a),xb = get(b);
name[xa].pb(xb);
}
bool success = false;
for(int i = 1;i <= 10;i ++)
{
for(int j = 4;j < name[i].size();j ++)
{
set<int> s;
for(int k = j - 4;k <= j;k ++) s.insert(name[i][k]);
if(s.size() == 5)
{
success = true;
break;
}
}
if(success) break;
}
if(success) cout << "PENTA KILL!" << endl;
else cout << "SAD:(" << endl;
return 0;
}
C. Jump and Treasure 单调队列优化dp + 调和级数
不懂 ，大爹队友写的
ac代码
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
const int N=1e6+5;
int a[N];
LL f[N],q[N],s[N];
int main()
{
ios;
int n,Q,p;
cin>>n>>Q>>p;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
int m=n/i;
int k=p/i;
int hh=0,tt=0;
q[0]=0;
f[0]=0;
for(int j=1;j<=m;j++)
{
while(q[hh]<j-k) hh++;
f[j]=f[q[hh]]+a[i*j];
while(hh<=tt&&f[q[tt]]<=f[j]) tt--;
q[++tt]=j;
}
int temp=0;
if((n+1-p)%i==0) temp=(n+1-p)/i;
else temp=temp=(n+1-p)/i+1;
while(q[hh]<temp) hh++;
s[i]=f[q[hh]];
}
while(Q--)
{
int x;
cin>>x;
if(x>p) puts("Noob");
else printf("%lld\n",s[x]);
}
return 0;
}
I. Cutting Suffix 思维
题意：将一个字符串的每个字母保留原有相对顺序分到两个集合里，要求让两个集合所对应的两个字符串的所有两两后缀的lcp之和最小
分析：
诈骗题：如果字符串中只有一种字符，则将一个字符放在一个集合里，其他的放另外一个，则所有lcp都是1，答案即为 |s|
- 1,如果存在多个字符，则答案为0
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
//#define int long long
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 1e9 + 1;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
int main()
{
ios;
string s;
cin >> s;
vector<int> a(30);
for(char c : s) a[c - 'a'] ++;
int cnt = 0;
for(int i = 0;i < 26;i ++) if(a[i]) cnt ++;
if(cnt == 1) cout << s.size() - 1 << endl;
else cout << 0 << endl;
return 0;
}
J. Balanced Tree
题意：定义平衡二叉树为左右子树均为平衡二叉树，且左右子树大小差别不超1，给定n，求节点数为n的平衡二叉树的个数
分析：手玩几个样例可以发现答案是可以递推出来的递推式为
根据上式可以看出答案一定是2的整次幂，但乘法递推比较麻烦，我们用对数函数进行变形
\[g(x)= \begin{cases} g(\frac{x}{2}) + g(\frac{x}{2} - 1) + 1, & \text {if $x$ is even} \\ 2g(\frac{x - 1}{2}), & \text{if $x$ is odd} \end{cases} \]我们记\(g(x) = a*g(\frac{x - 1}{2}) + b * g(\frac{x - 1}{2} - 1) + c\),则
\[g(x)= \begin{cases} a*[g(\frac{x}{2}) + g(\frac{x}{2} - 1)] + 2b * g(\frac{x - 1 - 1}{2}) + a + c, & \text {if $x$ is even} \\ 2a *g(\frac{x - 1}{2}) + b * [g(\frac{x - 1}{2}) + g(\frac{x - 1}{2} - 1)] + b + c & \text{if $x$ is odd} \end{cases} \]\[= \begin{cases} a*g(\frac{x}{2}) + (a + 2b) * g(\frac{x}{2} - 1) + a + c, & \text {if $x$ is even} \\ (2a + b) *g(\frac{x - 1}{2}) + b * g(\frac{x - 1}{2} - 1) + b + c & \text{if $x$ is odd} \end{cases} \]初始时我们令\(g(n) = 1 * g(\frac{n - 1}{2}) + 0 * g(\frac{n - 1}{2} - 1) + 0\)
当\(n = 1\)时，\(g(1) = a*g(0) + b*g(-1) + c = c\)
然后每次除2根据奇偶判断改变系数的值，最终的c既是所求答案的幂次
所以$ans = 2 ^c \ mod \ 2^{64} \(
可以发现\)c >= 64$ 时，答案一定为0
ac 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
//#define int long long
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 1e9 + 1;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
void dfs(uLL x,uLL a,uLL b,uLL & c)
{
if(x <= 1) return ;
if(x & 1)
{
c += b;
a = a + a + b;
dfs((x - 1) / 2,a,b,c);
}
else
{
c += a;
b = b + b + a;
dfs(x / 2,a,b,c);
}
}
int main()
{
ios;
cin >> t;
while(t --)
{
uLL x;
cin >> x;
uLL c = 0;
dfs(x,1,0,c);
uLL ans = 1;
if(c < 64) ans <<= c;
if(c >= 64) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}
K. aaaaaaaaaaA heH heH nuN 思维 + 二进制
题意：形如 nunhehheh + 若干个a 这种称为优雅串.
给定 n，构造恰好有 n 个子序列是优雅串的字符串
分析：我们仅考虑前缀nunhehheh后仅有n个a的字符串，可以发现这样的字符串所含优雅串的个数为
\(C_n^1 + C_n^2 + C_n^3 + C_n^4 + ... + C_n^n = 2^n - 1\)
所以n个a对答案的贡献为\(2^n - 1\),看到这很容易想到数的二进制表示，我们求出所给数字n的最高位1的位数,用这么多a去表示，当二进制中为1时我们在a的倒数该位数个a前加一个h
最后，我们离答案还差x个,x为n的二进制表示中1的个数，这个只要在最后一个a前面补x个h即可
ac代码
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
int n,m,k,t;
string f(int n)
{
string res;
while(n) res += char('0' + n % 2),n /= 2;
reverse(all(res));
return res;
}
int main()
{
ios;
cin >> t;
while(t --)
{
cin >> n;
if(n == 0)
{
cout << "nunhehheh" << endl;
continue;
}
if(n == 1)
{
cout << "nunhehheha" << endl;
continue;
}
//cout << f(n) << endl;
int cnt ,idx = 0,x = 0;
vector<int> bin;
for(int k = 0;k <= 31;k ++) if(n >> k & 1) bin.pb(k),cnt = k,x ++;
string res,tp;
for(int i = 0;i < cnt;i ++)
{
if(idx < bin.size() && i == bin[idx]) res += 'h',idx ++;res += 'a';
}
idx = 0;
while(res[idx] == 'h') idx ++;
idx ++;
while(x --) tp += 'h';
res = res.substr(0,idx) + tp + res.substr(idx);
reverse(all(res));
cout << "nunhehheh" << res << endl;
}
return 0;
}
L. Collecting Diamonds
题意：
• 长度为 n 的只含有 ABC 的字符串.
• 选择连续的三个位置 ABC，如果 A 在奇数位置就删去 AC；否则删去 B.
• 最大化操作数.
思路：
• 注意到如果操作删除 B 则当前 ABC 组不可能继续操作，并
且也只有删除 B 才能更改后面的 ABC 组的奇偶性.
• 所以应该尽量让每个组都操作一次删除 B，并尽量保证在操
作删除 B 之前删除尽量多的 AC.
• 所以使用一个变量存储下前面一共删除了几次 B，便可以用
以计算可以删除多少个 AC.
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
//#define int long long
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 1e9 + 1;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
int main()
{
string s;
cin >> s;
n = s.size();
s = ' ' + s + ' ';
vector<int> p(n + 1);
vector<bool> st(n + 1);
for(int i = 1;i <= n;i ++)
{
if(s[i] == 'B')
{
for(int j = 1;;j ++)
{
if(s[i - j] != 'A' || s[i + j] != 'C')
{
if(j != 1)
{
p[i] = j - 1;
st[i] = true;
}
break;
}
}
}
}
int ans = 0,cnt = 0;
for(int i = 1;i <= n;i ++)
{
if(s[i] == 'B' && st[i])
{
if(!cnt)
{
if(i & 1)
{
cnt ++,ans ++;
}
else
{
if(p[i] == 1) ans ++;
else cnt ++ ,ans += 2;
}
continue;
}
ans += min(p[i],(i % 2 == 0) + cnt + 1);
cnt ++;
}
}
cout << ans << endl;
return 0;
}