7月18号的比赛，一直拖着没补。想想就这样放着不太行，还是开个坑慢慢填吧
考前一个月备战期末没摸acm，最后rank85/265,罚时卡出ag线，大概就是报应吧。
D. Journey to Un'Goro
构造。
很关键的一个想法：令(p_i)表示从(1)到(i)位置中(r)数量的奇偶性，(i)到(j)中(r)的数量为奇数的条件便是(p_{i-1},p_j)不同。(特别地，(p_0)为偶)
那么对于(n)的一种构造方式，考虑有(x)个奇数点，(n+1-x)个偶数点,那么题中要求的((i,j))对数就是(x*（n-x+1）)。均值不等式，想要最大化合法对数就是使得奇偶点数为(lceilfrac{n+1}{2} ceil)和(lfloorfrac{n+1}{2} floor)（谁大谁小都行），然后就排列就是了。由于从第(0)位开始且该位确定是偶，所以排列确定，你的(br)序列也就定了。排列中当前位与前一位不同,这一位就是(r)，反之是(b)。
那么dfs就行了，贪心从前往后做一位一位的做，在满足奇偶点的数量约束的前提下（(lceilfrac{n+1}{2} ceil)），优先保证当前位与前一位奇偶相同（也就是填(b)），搜到了100个答案就直接终止。
#include<bits/stdc++.h>
using namespace std;
int n,tot=0;
int ans[100005],num[2];
void dfs(int len)
{
if(tot>=100)
return;
if(len>n)
{
for(int i=1;i<=n;i++)
{
if(ans[i]==ans[i-1])
printf("b");
else
printf("r");
}
tot++;
if(tot>=100)
exit(0);
printf("
");
return;
}
int p=ans[len-1];
if(num[p]<n/2+1)
{
num[p]++;
ans[len]=p;
dfs(len+1);
num[p]--;
}
p=p^1;
if(num[p]<n/2+1)
{
num[p]++;
ans[len]=p;
dfs(len+1);
num[p]--;
}
}
int main()
{
scanf("%d",&n);
long long p=n;
ans[0]=0;
num[0]=1;
num[1]=0;
printf("%lld
",(p+1ll)/2ll*(p/2ll+1ll));
dfs(1);
return 0;
}
H. The Boomsday Project
传送门
先考虑怎么暴力
显然你一定是把一张优惠卡用到不能用了（时间限制或次数限制）
将每次租车按时间排序，(dp[i])表示恰好处理完前(i)次租车的最小花费，(f[i][j])表示在第(i)次用第(j)张卡，能覆盖到的最后租车是那次，(f)数组可以二分查找来得出
转移:
[dp[i+f[i+1][j]]=max(dp[i]+c,dp[i+f[i+1][j]])
]
[dp[i+1]=max(dp[i+1],dp[i]+r)
]
再考虑怎么优化掉这个(log)
注意到(f)数组具有单调性：
[f[i+1][j]>=f[i][j]
]
事实上我们每次算(f[i][j])时，只需要从(f[i-1][j])开始递推，一个一个地往后挪即可
特别地，为了防止MLE，f数组需要使用滚动数组
#include<bits/stdc++.h>
using namespace std;
int n,m,r,p,q,cnt=0;
int d[505],k[505],c[505],rt[300005],f[2][505];
long long dp[300005];
int main()
{
memset(f,0,sizeof(f));
scanf("%d%d%d",&n,&m,&r);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&d[i],&k[i],&c[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p,&q);
for(int j=cnt+1;j<=cnt+q;j++)
{
rt[j]=p;
dp[j]=1e18;
}
cnt+=q;
}
sort(rt+1,rt+1+cnt);
dp[0]=0;
rt[0]=0;
for(int i=0;i<=cnt-1;i++)
{
dp[i+1]=min(dp[i+1],dp[i]+1ll*r);
for(int j=1;j<=n;j++)
{
for(int l=f[0][j];l<=cnt;l++)
{
if(l-i<=k[j]&&rt[l]-rt[i+1]<=d[j]-1)
f[1][j]=l;
else
break;
}
f[0][j]=f[1][j];
dp[f[0][j]]=min(dp[i]+1ll*c[j],dp[f[0][j]]);
//printf("%d %d %d %lld %lld
",i,j,f[0][j],dp[i],dp[i+f[0][j]]);
}
}
printf("%lld",dp[cnt]);
return 0;
}