今天是2018/7/15
然后又是我最不喜乱的测试，期末考试爆炸仍在眼前。
T1 van♂游戏
题意
小喵喵喜欢玩RPG游戏。在这款游戏中，玩家有两个属性，攻击和防御，现在小喵喵的攻击和防御都是1，接下来小喵喵会依次遇到n个事件。事件有两种。
1.小喵喵经过修炼，角色升级了，此时可以选择攻击+1或者防御+1.
2.小喵喵遇到了一个敌人，可以选择战斗或者逃跑。如果战斗，胜利后得到a[i]金钱。如果逃跑，则无事发生，但是以后也不能再回来打这个怪物了。
对于一场战斗来说，如果小喵喵的攻击力大于等于atk[i]，防御力大于等于def[i]，那么他可以无伤打败这只怪物，从而他选择打怪，否则他发现自己会受伤，从而选择逃跑。
现在小喵喵想知道，通过巧妙地选择升级时加的属性，他最多能够从这n个事件中获得多少金钱。
这是一道dp题，首先我们可以确定，同一时间内状态叔很少，空间是可以的。
Q：我们设f[i]表示攻击力为i时的收益。为什么不多加一维储存防御力呢？
A：技能点数是一定的，我们可以通过枚举攻击力算出来防御力，这也是为什么同一时间内状态数小的原因。
然后我们开始讨论转移。
当升级时，一种状态：攻击力为i，防御力为j
可以转移为攻击力i+1，防御力j和攻击力i，防御力j+1的两种状态
写出来就是f[i]=max(f[i],f[i-1]); i from tot(总技能点数) to 1 这里是间接转移了防御力。
然后对于打怪，就是按照题意比较转移就可以了
#include<cstdio>
#include<iostream>
#include<algorithm>
using std::max;
int read()
{
char c=getchar();
int res=0;
while(c=='
'||c==' ') c=getchar();
if(c=='U'||c=='M') return c;
while(c>='0'&&c<='9')
{
res=res*10+c-'0';
c=getchar();
}
return res;
}
long long f[2020];
int main()
{
int n=read();
int opt,tot=2;
long long ans=0;
for(int i=1;i<=n;i++)
{
opt=read();
if(opt=='U')
{
tot+=1;
for(int i=tot-1;i;i--)
f[i]=max(f[i],f[i-1]);
}
else
{
int a=read(),b=read(),c=read();
for(int j=1;j<tot;j++)
{
int atk=j,def=tot-j;
if(atk>=b&&def>=c)
f[atk]+=1LL*a;
}
}
}
for(int i=1;i<tot;i++)
ans=max(ans,f[i]);
printf("%lld",ans);
}
/*
5
U
M 123 1 2
M 1234 2 1
U
U
*/
这题还算简单，屁嘞
T2
题意
小喵喵家附近有n个路口，m条道路连接着这些路口，而且通过这些道路各自需要一些时间c[i]。
小喵喵在1号路口，他要去n号路口上学，但是他马上要迟到了，所以他想知道最短需要多长时间能够到达学校。
其中忽略小喵喵由于出家门、到n号路口之后进入学校、从一条道路移动到另一条道路之类的时间，只计算他在这些道路上花费的时间总和。
分成图，好不容易用对了一次树状数组，结果longlng暴了我两个麻痹戒指。
结果就只有50了
//修正后
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using std::min;
using std::queue;
const int maxn=1010;
int dis[maxn][15],head[maxn],nxt[maxn];
bool inque[maxn][15];
int n,m,k;
int tail=0;
int read()
{
int res=0;char c=getchar();
while(c>'9'||c<'0') c=getchar();
while(c>='0'&&c<='9')
{
res=res*10+c-'0';
c=getchar();
}
return res;
}
struct node
{
int point;
int weight;
int nxt;
};
node line[21000];
void add(int x,int y,int z)
{
line[++tail].point=y;
line[tail].nxt=head[x];
line[tail].weight=z;
head[x]=tail;
}
void updata(int pos,int now,int val)
{
while(now<=k+1)
{
dis[pos][now]=min(dis[pos][now],val);
now+=(now&(-now));
}
return ;
}
int check(int pos,int now)
{
int res=0x7fffffff;
while(now)
{
res=min(dis[pos][now],res);
now-=(now&(-now));
}
return res;
}
struct data
{
int p;
int k;
};
void SPFA()
{
queue<data>q;
data pas;pas.k=1,pas.p=1;
memset(dis,1,sizeof(dis));
dis[1][1]=0;
inque[1][1]=true;q.push(pas);
while(!q.empty())
{
pas=q.front();q.pop();
inque[pas.p][pas.k]=false;
for(int i=head[pas.p];i;i=line[i].nxt)
{
if(check(line[i].point,pas.k)>dis[pas.p][pas.k]+line[i].weight)
{
updata(line[i].point,pas.k,dis[pas.p][pas.k]+line[i].weight);
if(!inque[line[i].point][pas.k])
{
inque[line[i].point][pas.k]=true;
data nxt;
nxt.p=line[i].point;nxt.k=pas.k;
q.push(nxt);
}
}
if(check(line[i].point,pas.k+1)>dis[pas.p][pas.k]&&pas.k<k+1)
{
updata(line[i].point,pas.k+1,dis[pas.p][pas.k]);
if(!inque[line[i].point][pas.k+1])
{
inque[line[i].point][pas.k+1]=true;
data nxt;
nxt.p=line[i].point;nxt.k=pas.k+1;
q.push(nxt);
}
}
}
}
}
int main()
{
freopen("school.in","r",stdin);
freopen("school.out","w",stdout);
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)
{
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,c);
}
SPFA();
int ans=0x7fffffff;
for(int i=1;i<=k+1;i++)
ans=min(ans,dis[n][i]);
printf("%d",ans);
}
/*
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2
*/
t3（van♂全想偏系列）
我先看看去
题目描述
定义一个数列的代价如下：
每次操作可以选择一个区间，和一个2的幂次，使得这个区间的所有数字减去这个2的幂次。最少的使得这个数列全部减为0的操作次数即为这个数列的代价。注意在减的时候要求二进制下这个区间的所有数字都要是1，即在二进制下，这个减法不能退位。
例如：5 2 2中，不能进行[1,3]减去2的操作，因为(5)10=(101)2,在第二位不是1，所以不能减。
又如：7 5 3数列的代价为4，可以进行如下操作：[1,3]减1，[1,2]减4，[1,1]减2，[3,3]减2.
小喵喵有一个长度为n的数列a[i]。他想知道a[i]的所有子序列（可以是不连续的）的代价之和。因为这个数字可能非常大，你只需要输出ans%998244353的结果就可以了。
然而我自己并不会想出来，不过是真妙♂呀
首先考虑如果只有0和1是什么情况。
此时一个数列的代价就是数出连续1的段数。
考虑cnt[i][0/1]表示对于前i个数的子序列，最后一位是0/1的方案数有多少。
Sum[i][0/1]表示对于前i个数的子序列，代价和是多少。
转移方程：
···
if ( b[i] == 0 ) {
cnt[i][0] = ( 2 * cnt[i-1][0] + cnt[i-1][1] + 1 ) % mod;
cnt[i][1] = cnt[i-1][1];
sum[i][0] = ( sum[i-1][0] * 2 + sum[i-1][1] ) % mod;
sum[i][1] = sum[i-1][1];
}
else {
cnt[i][0] = cnt[i-1][0];
cnt[i][1] = ( cnt[i-1][0] + 2 * cnt[i-1][1] + 1 ) % mod;
sum[i][0] = sum[i-1][0];
sum[i][1] = ( sum[i-1][0] + cnt[i-1][0] + 2 * sum[i-1][1] + 1 ) % mod;
}
···
对于其他情况，我们只需要多开记录在二进制上的第几位就可以了