A. PENTA KILL!
签到题，直接O( n 2 n^2 n2)遍历每一个五杀的开始点然后计算是否符合规则即可。规则就是一个人必须连续杀死五个不同的敌人，这个五杀者可在此过程中死亡。
const int N=200010,M=N*2,mod=1e9+7;
int n,m,k,a[N];
struct F{
string p,q;
}v[N];
map<string,set<string>> mp;
void solve(){
cin >> n;
rep(i,1,n){
cin >> v[i].p >> v[i].q;
}
bool ok=false;
for(int i=1;i<=n;++i){
string p=v[i].p,q=v[i].q;
mp[p].clear();
for(int j=i;j<=n;++j){
if(v[j].p==p){
if(mp[p].count(v[j].q)) break;
else{
mp[p].insert(v[j].q);
if(mp[p].size()==5) {ok=true; break;}
}
}
}
}
if(ok) cout << "PENTA KILL!\n";
else cout<<"SAD:(\n";
}
B. Prime Ring Plus
大意：给定1~n，n个数，让你构造k个环是的环上相邻数字和为质数。
这道题在赛场上我是先看的题目，想了一遍常规方法发现并不是很好解决。不知道是不是比赛的时候把数据范围给看错了，赛后刷了知乎后又看了遍题目，才发现这道二分图还是蛮明显的。
建图方式：
1.建立源点S和汇点T，将n个数分成奇数和偶数
2.从S向所有奇数连容量为2的边，从所有偶数向T连容量为2的边，然后奇数向所有与之和为质数的偶数连容量为1的边（因为每个点在环上都相当于和两个数相连接，因此当两数之间满流的时候说明两数存在一个环内）
3.遍历所有中间容量为1的正向边，如果满流则说明当前跑出来的可行解中这两个点在一个环内，我在这里先根据所有点的度数判断解存不存在，然后dfs出最终答案。
Code
const int N = 100010,INF=0x3f3f3f3f, M = 5000*2500*2+10000;
bool numlist[N];
int prime[N],cnt;
void Eular(int n=20000){
for(int i=2;i<=n;i++){
if(!numlist[i])
prime[++cnt]=i;
for(int j=1;prime[j]<=n/i;j++){
numlist[i*prime[j]] =true;
if(i%prime[j]==0)
break;
}
}
return ;
}
int n,m,F,D,S,T;
int e[M],ne[M],h[N],f[M],idx=0;
int cur[M],q[N],d[N];
int du[N],vis[N];
vector<int> edge[N];
vector<int> ans[N];
int dx=0;
void add(int a,int b,int c){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
int find(int u,int limit){
if(u == T) return limit;
int flow = 0;
for(int i=cur[u];~i && flow < limit ;i=ne[i]){
cur[u] = i;
int ver = e[i];
if(d[ver] == d[u] + 1 && f[i]){
int t = find(ver,min(f[i],limit - flow));
if(!t ) d[ver] = -1;
f[i] -= t, f[i^1] += t, flow += t;
}
}
return flow;
}
bool bfs(){
memset(d,-1,sizeof d);
int hh = 0, tt = 0;
q[0] = S, cur[S] = h[S], d[S] = 0;
while(hh <= tt){
int u = q[hh ++];
for(int i=h[u];~i;i=ne[i]){
int ver = e[i];
if(d[ver] == -1 && f[i]){
d[ver] = d[u] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
q[++ tt] = ver;
}
}
}
return false;
}
int dinic(){
int ans = 0, flow = 0;
while(bfs()) while(flow = find(S,INF)) ans += flow;
return ans;
}
void dfs(int u){
vis[u]=1;
ans[dx].push_back(u);
for(auto v:edge[u]){
if(!vis[v]){
dfs(v);
}
}
}
void solve(){
n=read();
S=0,T=n+5;
for(int i=1;i<=n;++i){
if(i&1) add(S, i, 2);
else add(i, T, 2);
}
for(int i=1;i<=n;i+=2){
for(int j=1;j<=n/2;++j){
if(!numlist[i+2*j]){
add(i, 2*j, 1);
}
}
}
dinic();
// int cc=0;
for(int i=0;i<idx;i+=2){
if(e[i]!=T&&e[i^1]!=S&&!f[i]){
int a=e[i^1],b=e[i];
// printf("%d---->%d:%d\n",e[i^1],e[i],f[i]);
du[a]++,du[b]++;
// cc++;
edge[a].push_back(b);
edge[b].push_back(a);
}
}
// debug(cc);
bool ok=true;
for(int i=1;i<=n;++i)
if(du[i]!=2) {
ok=false;
break;
}
if(!ok){
print(-1);
return ;
}
for(int i=1;i<=n;++i){
if(!vis[i]){
++dx;
dfs(i);
}
}
print(dx);
for(int i=1;i<=dx;++i){
printf("%d ",ans[i].size());
for(auto u:ans[i]){
printf("%d",u);
if(u!=ans[i].back()) printf(" ");
}
printf("\n");
}
}
倒是补题中途被欧拉筛坑了几下，最大的可能出现的质数应该是2e4以内，我一开始开小了…
C. Jump and Treasure
C题的DP式子很简单，就是令f[i]表示在i位置的最大值，有
f
[
i
]
=
m
a
x
{
f
[
i
?
k
?
j
]
}
(
k
?
j
≤
p
)
f[i]=max\{f[i-k\cdot j]\} (k\cdot j \le p)
f[i]=max{f[i?k?j]}(k?j≤p),其中j表示当且为jlevel.
然后我的第一反应是写线段树，当时计算了一下发现3e8感觉有点悬。然后队友说这有点向单调队列优化的背包（模数优化），然后我反应过来确实单调队列可以行，然后就正常写即可，复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
#define int LL
const int N = 1000010;
const LL INF = 1e17;
LL n,m,p,a[N],ans[N];
vector<int> qry[N];
vector<LL> vec;
int q[N],hh,tt;
void solve(){
n=read(),m=read(),p=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i){
int x=read();
if(x>p) ans[i]=-INF;
else qry[x].push_back(i);
}
for(int i=1;i<=n;++i){
if(qry[i].size()){
vec.clear();
vec.push_back(0);
for(int j=i;j<=n;j+=i)
vec.push_back(j);
vec.push_back(n+1);
vector<LL> f(vec.size()+20,-INF);
f[0]=0;
hh=0,tt=-1;
q[++tt]=0;
for(int j=1;j<vec.size();++j){
while(hh<=tt&&vec[j]-vec[q[hh]]>p) hh++;
f[j]=max(f[j], f[q[hh]]+a[vec[j]]);
while(hh<=tt&&f[q[tt]]<=f[j]) tt--;
q[++tt]=j;
}
for(auto id:qry[i])
ans[id]=f[vec.size()-1];
}
}
for(int i=1;i<=m;++i){
if(ans[i]==-INF) puts("Noob");
else print(ans[i]);
}
}
J. Balanced Tree
赛时是队友打表过的，当时一开始想着记忆化然而发现并不行。看了一下题解，是用递推来算。我想了一下，大概是用记忆化拆开后发现利用了影响2*i-1和2*i的是相同的两个数，因此写成两个数的递推关系。
令 g ( n ) = a ? g ( x ) + b ? g ( x ? 1 ) + c g(n)=a\cdot g(x)+b\cdot g(x-1)+c g(n)=a?g(x)+b?g(x?1)+c
若x为偶数，则有 g ( n ) = a ? g ( x 2 ) + ( a + 2 b ) ? g ( x 2 ? 1 ) + a + c g(n)=a\cdot g(\frac{x}{2})+(a+2b)\cdot g(\frac{x}{2}-1)+a+c g(n)=a?g(2x?)+(a+2b)?g(2x??1)+a+c
若x为奇数，则有 g ( n ) = ( 2 a + b ) ? g ( x ? 1 2 ) + b ? g ( 2 ? 1 2 ? 1 ) + b + c g(n)=(2a+b)\cdot g(\frac{x-1}{2})+b\cdot g(\frac{2-1}{2}-1)+b+c g(n)=(2a+b)?g(2x?1?)+b?g(22?1??1)+b+c
然后 l o g n logn logn层递推 g ( n ) = x g ( 1 ) + y g ( 0 ) + z g(n)=xg(1)+yg(0)+z g(n)=xg(1)+yg(0)+z就是最终答案，如果大于等于64就是0，否则直接输出相应2的幂次。
ULL n;
LL dfs(ULL x,LL a,LL b,LL c){
if(x==0) return 0;
if(x==1){
return c;
}
if(x&1)
return dfs((x-1)/2,2ll*a+b,b,b+c);
else
return dfs(x/2,a,a+2ll*b,a+c);
}
void solve(){
cin >> n;
LL res=dfs(n,1,0,0);
if(res>=64) cout << 0 << "\n";
else {
ULL ans=1;
rep(i,1,res) ans *= 2;
cout << ans << "\n";
}
}
K. aaaaaaaaaaA heH heH nuN
这道构造题和五月份昆明的那一道几乎是一样的套路，用二进制拼凑的思想。我们发现对于ha...ak个a的贡献是
2
k
?
1
2^k-1
2k?1,而如果以h...ha(p个h)结尾的贡献是p,那么我们只要按位凑出来再最后把1加上去即可。
int n;
vector<int> pos;
void solve(){
pos.clear();
cin >> n;
int cnt=0;
for(int i=30;i>=0;--i)
if(n>>i&1)
pos.push_back(i);
if(n==0){
cout << ("h\n");
return ;
}
else if(n==1){
cout << ("nunhehheha\n");
return ;
}
if(pos.back()==0) cnt++,pos.pop_back();
cnt += pos.size();
string ans="nunhehheh";
for(int i=0;i<pos.size();++i){
if(i==pos.size()-1){
int tmp=pos[i];
rep(j,1,tmp-1) ans += "a";
rep(j,1,cnt) ans += "h";
ans+="a";
break;
}
int tmp=pos[i]-pos[i+1];
rep(j,1,tmp)
ans += "a";
ans += "h";
}
cout << ans << "\n";
}
I. Cutting Suffix
很经典的一道诈骗题，刚看到的时候想到了各种奇奇怪怪的字符串算法，但是看到过题人数很快我就知道大概是个思维之类的。很快发现：
如果这个字符串由单一字符构成，那么我们就只把最后一个后缀(单个字母)放在一个集合，其他的放在另外一个集合，答案为s.size()-1
否则，随便选择一个字符，把所有这个字符开头的后缀都放进一个集合中，其他的放入另一个集合，因此答案就是0
string p;
int num[29];
void solve(){
int cnt=0;
cin >> p;
for(int i=0;i<p.size();++i){
num[p[i]-'a'] ++;
if(num[p[i]-'a']==1) cnt++;
}
if(cnt==1){
print(p.size()-1);
return ;
}
print(0);
}
L. Collecting Diamonds
L题很可惜啊，当时做这道题还有将近1h40min,只要能搞出来就是金牌了，but性质之类的都想出来了，卡在最后代码没写好…
我又简洁了一下做法，延续着我比赛时候的思路：
首先双指针与处理出每一段形如A...ABC...C形式的字符串（舍弃B左右不含A或者C的）。
性质：
1.删AC可以在没有删完的情况下一直删，且不影响后面串的奇偶性
2.删B只能对于每一
段删一次，而且删完之后这一段剩余的AC就没有用了，但是删B可以改变后面串奇偶性使得后面可以可持续化删AC。因此删B的妙处就在这里3.如果对于删AC或者删B都行的但是只能删一次的ABC我们删B更优
总结一下：在每一段都能删B的情况下我们尽量把所有能删的AC都删了，这就是贪心策略
因此遍历整个串的每一段，分成两种情况：
1.前面还没有能够改变奇偶性的
此时如果只能删AC那就ans++
否则选择删B,ans++并且被删B的数量的计数器cnt++,意味着后面的奇偶性能够被改变了
2.前面已经有能够改变后面奇偶性的B出现了
能删的次数就是min(q[i].x, (q[i].y==0)+cnt+1)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define x first
#define y second
typedef pair<int,int> pii;
string s;
int n,hh,tt;
pii q[N];
void solve() {
hh=0,tt=-1;
cin >> s;
for(int i=0;i<s.size();++i){
if(s[i]!='B') continue;
int l=i,r=i;
while(l-1>=0 && s[l-1]=='A') l--;
while(r+1<s.size() && s[r+1]=='C') r++;
if(min(r-i,i-l)>0)
q[++tt]=make_pair(min(r-i,i-l),(i+1)%2);
i=r;
}
int ans=0,cnt=0; //答案和可以删B的次数
for(int i=0;i<=tt;++i){
if(cnt==0){
if(q[i].y==0){
if(q[i].x==1) ans++;
else ans += 2, cnt ++;
}
else
ans ++,cnt ++;
}
else{
ans += min(q[i].x, (q[i].y==0)+cnt+1);
cnt ++;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
相关推荐：
