比赛地址
Deep
题目描述
失败的燃烧军团想要逃回深渊，Khadgar 想要追击它们。
然而进入深渊的传送门只有一座，燃烧军团和 Khadgar 各有一些法力水晶，由 Khadgar 先手，双方每次可以作出如下选择：
- 使用一个法力水晶，使得传送门的法力等级增加一。
- 不用法力水晶，让对方增加等于传送门法力等级的深度，然后将传送门的法力值清零。特别地，若法力水晶数不为零且传送门法力等级为零则不能进行这样的操作。
双方都会采取最优策略使自己的最终深度与对手深度的差最大（初始时深度均为零）。
现在多次给定双方起始的法力水晶数量 A, B，求 Khadgar 与燃烧军团的的最终深度差。
思路
结论题。对于 A, B 均为正整数的时候答案就是 A − B − 2，否则特判掉即可。
代码
为什么要写快读，这不是 $O(T)$ 做法嘛？
因为我用 cin cout 写的程序只有 40分，尽管是 $O(T)$ 但是它还是 T 了。
#include
using namespace std;
struct ios{
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template inline ios & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
}io;
int main(){
int T,a,b;
io>>T;
while(T--){
io>>a>>b;
if ((a*b)) printf("%d\n",a-b-2);
else if (!a) printf("%d\n",-b);
else printf("%d\n",a);
}
} Dark
题目描述
给定一个长为 $n$ 的序列，每次可以选定两个相邻的正整数令它们均减1，直到不能进行更多操作。求最少的操作次数。
思路
看数据范围可以写一个 $O(\sum A_i)$的 dp。
令 $dp_{i,j,1/0}$ 为考虑到第 $i$ 个数，这个数余下的值为 $j$，前一个数是否为零。
代码
#include
#define maxn 5000101
#define oo 0x3f3f3f3f
using namespace std;
int dp[maxn][2],tem[maxn][2],suf[maxn];
int ans=oo,a[maxn],n,top;
void work(){
for (int i=0;i<=top;i++)
dp[i][0]=dp[i][1]=suf[i]=oo;
dp[0][0]=suf[0]=0;
for (int i=1;i<=n;i++){
for (int j=a[i-1]+1;j<=a[i];j++)
dp[j][0]=dp[j][1]=suf[j]=oo;
for (int j=a[i];~j;j--){
tem[j][0]=tem[j][1]=oo;
tem[j][0]=min(tem[j][0],a[i]-j+suf[a[i]-j]);
tem[j][0]=min(tem[j][0],a[i]-j+dp[a[i]-j][0]);
tem[j][1]=min(tem[j][1],a[i]-j+dp[a[i]-j][0]);
}
suf[a[i]+1]=oo;
for (int j=a[i];~j;j--){
dp[j][0]=tem[j][0];
dp[j][1]=tem[j][1];
suf[j]=min(suf[j+1],dp[j][1]);
}
}
ans=dp[0][0];
for (int i=0;i<=a[n];i++) ans=min(ans,dp[i][1]);
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i],top=max(top,a[i]);
work();
cout< Fantasy
题目描述
给定一个长度为 $n$ 的序列，求 $k$ 个不同的长度在 $L,R$ 之间的数字和最大的字串。