借了某神仙的号来打Div2，结果手速过C之后莽了个错误结论。好不容易把结论改对了结果喜闻乐见被DDos攻击了？（上次DDos好像也是Technocup吧）
之后就果断颓废了
A
特判2，之后奇数答案为1，偶数答案为0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
int q=read();
while (q--)
{
int n=read();
if (n==2) puts("2");
else if (n&1) printf("%d
",1);
else puts("0");
}
return 0;
}
B
不难发现你可以把一个字符串统一成只由一个原串中出现的字母，然后就变成了判断两个字符串是否有相同字符了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,tax[40];
char s[1010],t[1010];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
int q=read();
while (q--)
{
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1);
rep(i,1,n) tax[s[i]-'a']=1;
int ok=0;
rep(i,1,n)
if (tax[t[i]-'a']) {ok=1;break;}
if (ok) puts("YES");else puts("NO");
rep(i,0,26) tax[i]=0;
}
return 0;
}
C
答案具有二分性于是考虑二分答案。预处理每一个位置对捐赠值的贡献，二分所需天数，暴力贪心填就可以了，时间复杂度貌似被写成了(O(qnlog^2n))，似乎可以1个(log)(但是能过还管他干嘛)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define int long long
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,a[200200],pri[200200],p[200200],lim,tmp[200200];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
bool chk(int len)
{
rep(i,1,len) tmp[i]=a[i];
sort(tmp+1,tmp+1+len);
reverse(tmp+1,tmp+1+len);
ll ans=0;
rep(i,1,len)
{
ans+=pri[i]*tmp[i];
if (ans>=lim) return 1;
}
return 0;
}
signed main()
{
int q=read();
while (q--)
{
n=read();
rep(i,1,n) pri[i]=read()/100;
sort(pri+1,pri+1+n);
reverse(pri+1,pri+1+n);
rep(i,1,n) a[i]=0;
int pro1=read(),gap=read();
for (int i=gap;i<=n;i+=gap) a[i]+=pro1;
pro1=read();gap=read();
for (int i=gap;i<=n;i+=gap) a[i]+=pro1;
lim=read();int l=1,r=n,ans=-1;
while (l<=r)
{
int mid=(l+r)>>1;
if (chk(mid)) {ans=mid;r=mid-1;}
else l=mid+1;
}
printf("%lld
",ans);
}
return 0;
}
D
直接考虑哪些数字进行了操作比较麻烦，我们考虑那些没有进行的操作的数字，最后用总数字种类数减一下
不难发现未被操作的数字从小到大排序后一定是一段区间，这个用反证法就比较显然。之后就可以直接dp以(i)结尾的最长不操作的区间长度，判一下前一个数字的区间是否合法就可以了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,a[300100],x[300300],m,f[300300],l[300300],r[300300];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
int q=read();
while (q--)
{
n=read();
rep(i,1,n) x[i]=a[i]=read();
rep(i,0,n) {l[i]=maxd;r[i]=0;}
rep(i,1,n)
{
l[a[i]]=min(l[a[i]],i);
r[a[i]]=max(r[a[i]],i);
}
sort(x+1,x+1+n);
m=unique(x+1,x+1+n)-x-1;
rep(i,1,m)
if (l[x[i]]>r[x[i-1]]) f[i]=f[i-1]+1;
else f[i]=1;
int ans=0;
rep(i,1,m) ans=max(ans,f[i]);
printf("%d
",m-ans);
}
return 0;
}
E
感觉这个题就十分的套路
记(f_{i.0/1})表示(i)不能/能向上时，其子树的最大价值和。转移的话考虑所有的儿子是否往上连。记(f_{v,1}+w>f_{v,0})的点为好点。好点个数(<k)时直接暴力转移(max(f_{v,0}+w,f_{v,1}))。
否则我们需要选择最优的(k-1)个(f_{v,1}+w)进行转移，随便移个项得到可以将(f_{v,1}+w-f_{v,0})的值从大到小，前(k-1)大的儿子考虑向上走，对第(k)大的分类讨论，最后处理剩下的儿子。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{int to,nxt,cost;}sq[1001000];
int all=0,head[500500];
int n,k,tot=0;
ll f[500500][2];
pii son[500500];
bool cmp(pii p,pii q)
{
int v1=p.fir,v2=q.fir;
return f[v1][1]+p.sec-f[v1][0]>f[v2][1]+q.sec-f[v2][0];
}
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void add(int u,int v,int w)
{
all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;
}
void dfs(int u,int fu)
{
int cnt=0;
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v==fu) continue;
dfs(v,u);
if (f[v][1]+sq[i].cost>f[v][0]) cnt++;
}
if (cnt<k)
{
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v==fu) continue;
ll now=max(f[v][0],f[v][1]+sq[i].cost);
f[u][0]+=now;f[u][1]+=now;
}
}
else
{
tot=0;
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v==fu) continue;
son[++tot]=mp(v,sq[i].cost);
}
sort(son+1,son+1+tot,cmp);
rep(i,1,k-1)
{
int v=son[i].fir,w=son[i].sec;
f[u][0]+=(f[v][1]+w);
}
f[u][1]=f[u][0];
int v=son[k].fir,w=son[k].sec;
f[u][0]+=f[v][1]+w;
f[u][1]+=max(f[v][0],f[v][1]);
rep(i,k+1,tot)
{
int v=son[i].fir;
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=max(f[v][0],f[v][1]);
}
}
}
int main()
{
int T=read();
while (T--)
{
n=read();k=read();
rep(i,1,n-1)
{
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
}
dfs(1,0);
printf("%lld
",max(f[1][0],f[1][1]));
all=0;
rep(i,1,n) f[i][0]=f[i][1]=head[i]=0;
}
return 0;
}
F
感觉我做过这个题的原题
暴力的话就是枚举区间([l,r])然后暴力做一个栈
注意到([l,r])合法等价于([1,l-1])与([1,r])这两个区间的栈中元素完全一致
那么就只需要从头开始做一遍栈，沿途记录栈中元素的(hash)值，开个(map)记一下就可以了
似乎并没有卡自然溢出？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
#define bas 300007
int n,a[300300],tp,sta[300300];
map<ull,int> mp;
ull hsh[300300];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
int T=read();
while (T--)
{
n=read();
rep(i,1,n) a[i]=read();
tp=0;ll ans=0;mp.clear();mp[0]=1;
rep(i,1,n)
{
if ((tp) && (sta[tp]==a[i])) tp--;
else {sta[++tp]=a[i];hsh[tp]=hsh[tp-1]*bas+a[i];}
ans+=mp[hsh[tp]];mp[hsh[tp]]++;
}
printf("%lld
",ans);
}
return 0;
}