这么简单的题目没有AK（
计时器(timer)
题目：
每次可以加上\(2^n-1\)，问多少次变成\(x\)
题解：
因为较大的数大于较小的数的两倍，直接贪心的选最大的即可。
复杂度\(\Theta(T\log n)\)
代码：
#include<cstdio>
#define int long long
const int N=105,A=1000000000000000000;
int T,x,f[N],cnt;
inline void prework(){for(int i=2;i<=A;i<<=1)f[++cnt]=i-1;}
inline int calc(int x){
int res=0;
for(int i=cnt;i;i--)res+=x/f[i],x%=f[i];
return res-1;
}
signed main(){
for(freopen("timer.in","r",stdin),freopen("timer.out","w",stdout),prework(),scanf("%lld",&T);T--;)scanf("%lld",&x),printf("%lld\n",calc(x));
return fflush(stdout),fclose(stdin),fclose(stdout),0;
}
Boss战(boss)
题目：
有\(n\)个回合，01串\(s_i\)，如果\(s_i=0\)则第\(n\)个回合boss获得\(1\)层再生，你每回合可以造成\(x\)伤害，也可以使用毒药，让boss获得\(1\)层中毒，在boss有\(\ge1\)层再生时，使boss减少一层再生。回合结束时，一层再生可以让boss血量\(+r\),一层中毒可以使boss血量\(-p\)。有\(k\)瓶毒药。在\(n\)个回合后，问boss减小的最大血量。
题解：
假设不使用毒药，算出\(boss\)减少的血量。
在第\(i\)回合使用毒药时造成伤害为\(f_i\)。
若\(s_i=0\)，\(f_i=(n-i+1)*p\)
若\(s_i=1\)，\(f_i=(n-i+1)*(r+p)\)
排序贪心的选出前\(k\)大的即可。
可以证明，每次选取\(s_i=0\)时，前面所有的\(s_i=1\)都会被选取，此时中毒层数为\(0\)。
复杂度\(\Theta(n\log n)\)
如果使用双指针，复杂度可以优化到\(\Theta(n)\)
代码：
#include<cstdio>
#include<algorithm>
#define int long long
const int N=1000005;
int n,x,r,p,k,f[N],ans;
char s[N];
inline int cmp(int x,int y){return x>y;}
signed main(){
freopen("boss.in","r",stdin),freopen("boss.out","w",stdout),scanf("%lld%lld%lld%lld%lld%s",&n,&x,&r,&p,&k,s+1);
for(int i=1;i<=n;i++){
if(s[i]^'0')f[i]=(n-i+1)*(r+p),ans+=x-(n-i+1)*r;
else f[i]=(n-i+1)*p,ans+=x;
}
std::sort(f+1,f+n+1,cmp);
for(int i=1;i<=k;i++)ans+=f[i];
return printf("%lld\n",ans),fflush(stdout),fclose(stdin),fclose(stdout),0;
}
路径(path)
题目：
有一个无项图，\(n\)个点，\(m\)条边，找一条从\(1\)开始，到\(n\)结束的路径，需要满足条件：路径上\(u\to v\)需要满足\(a_u\le a_v\)。路径的权值定义为\(a_i\)去重后的个数，求最小权值。
题解：
将\(a_i\)相等的极大联通块缩点，后按权值大小连边，求\(1\to n\)的最长路径。
时间复杂度\(\Theta(n\alpha(n)+m)\)（并查集找\(a_i\)相等的极大联通块）
可以优化到\(\Theta(n+m)\)
代码：
#include<cstdio>
#include<queue>
const int N=200005,INF=0x3f3f3f3f;
int n,m,a[N],head[N],pedge,f[N],fa[N],size[N];
struct Pair{
int fi,se;
}e[N];
struct Edge{
int to,next;
}edge[N];
inline void ins(int u,int v){edge[++pedge]={v,head[u]},head[u]=pedge;}
inline void Max(int&x,int y){if(y>x)x=y;}
int find(int x){return x^fa[x]?fa[x]=find(fa[x]):x;}
inline void swap(int&x,int&y){x^=y^=x^=y;}
inline void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(size[x]<size[y])swap(x,y);
size[x]+=size[y],fa[y]=x;
}
int dp(int u){
if(f[u]!=-INF)return f[u];
for(int e=head[u];e;e=edge[e].next){
int v=edge[e].to;
Max(f[u],dp(v)+1);
}
return f[u];
}
int main(){
freopen("path.in","r",stdin),freopen("path.out","w",stdout),scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i),fa[i]=i,size[i]=1,f[i]=-INF;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v),e[i]={u,v};
if(a[u]==a[v])merge(u,v);
}
for(int i=1;i<=m;i++){
int u=find(e[i].fi),v=find(e[i].se);
if(u^v)a[u]<a[v]?ins(v,u):ins(u,v);
}
f[find(1)]=1;
int ans=dp(find(n));
return printf("%d\n",ans<0?0:ans),fflush(stdout),fclose(stdin),fclose(stdout),0;
}