HDU多校3
赛中3题，菜…
1003
签到题，将每个单词压缩成大写的首字母
1012
题意：给定两个长度都为n的排列P、Q以及一个一开始为空的序列R，每次操作你可以从P或Q中弹出最左边的一个数字放入R的最右边。给定R，求有多少种操作方式能生成序列R。
思路：动态规划，考虑R[i]是由P[j]还是Q[k]转移过来的，因为P和Q都是排列，所以可以确定当前j和k的值。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],c[N],dp[N][2],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr[N][2];
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
bool cal(ll x,ll y,ll i,ll p){
if(pr[i][p].fi==x&&pr[i][p].se==y)return 1;
else return 0;
}
void solve(){
scanf("%lld",&n);
L(i,1,n*2)dp[i][0]=dp[i][1]=0;
L(i,1,n){
scanf("%lld",&x);
a[x]=i;
}
L(i,1,n){
scanf("%lld",&x);
b[x]=i;
}
L(i,1,2*n){
scanf("%lld",&c[i]);
}
dp[0][0]=0;dp[0][1]=1;
pr[0][0]=pr[0][1]=mkp(0,0);
L(i,1,2*n){
x=a[c[i]];y=i-x;
if(cal(x-1,y,i-1,0))dp[i][0]+=dp[i-1][0];
if(cal(x-1,y,i-1,1))dp[i][0]+=dp[i-1][1];
pr[i][0]=mkp(x,y);
dp[i][0]%=mod;
y=b[c[i]];x=i-y;
if(cal(x,y-1,i-1,0))dp[i][1]+=dp[i-1][0];
if(cal(x,y-1,i-1,1))dp[i][1]+=dp[i-1][1];
pr[i][1]=mkp(x,y);
dp[i][1]%=mod;
//printf("%lld %lld\n",dp[i][0],dp[i][1]);
}
ans=(dp[n*2][0]+dp[n*2][1])%mod;
printf("%lld\n",ans);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll T=1;
scanf("%lld",&T);
while(T--)solve();
}
1009
题意：给定n个包裹，第i个包裹你只能再li到ri的时间内取走，小Q一次最多同时取k个，问小Q最多要取多少次包裹。
思路：贪心，按(li,ri)排序，将每个包裹放入优队（表示待取），优队按ri的值降序。如果当前li＞优队中r最大的，则需要将优队中所有的包裹取完；如果优队中的数量≥k，则将优队中的包裹全部取走。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],c[N],dp[N][2],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y;}q[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
if(u.x!=v.x)return u.x<v.x;
else return u.y<v.y;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr[N][2];
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
void solve(){
ans=0;
scanf("%lld%lld",&n,&m);
L(i,1,n)scanf("%lld%lld",&q[i].x,&q[i].y);
sort(q+1,q+n+1,cmp);
L(i,1,n){
while(!sp.empty()){
x=sp.top();
if(q[i].x>x){
ans++;num=0;
while(!sp.empty()&&num<m){
num++;
sp.pop();
}
}
else break;
}
sp.push(q[i].y);
}
while(!sp.empty()){
ans++;num=0;
while(!sp.empty()&&num<m){
num++;
sp.pop();
}
}
printf("%lld\n",ans);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll T=1;
scanf("%lld",&T);
while(T--)solve();
}
1002
题意：你有n个技能，每个技能有t[i]的施法时间，并在len[i]秒时间内对怪物持续造成伤害，每秒造成d[i][j] 的伤害。len[i]可以大于t[i]，效果类似灼烧伤害，在施法期间不能施放其他技能，每个技能只能释放一次。怪物的血量为m，请问最少多少时间可以杀死怪物。
思路：因为n很小只有18，所以考虑枚举每个技能是放还是不放。因为题目问的是最少时间，所以可以用二分时间简化问题。结合两者，二分时间后，考虑状压dp，枚举最后一步放的是哪个技能，由前面放的技能的状态转移而来即可，复杂度为O(n*2^n*log[max(len)])。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum[N],pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],c[20][N],d[N],dp[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
bool check(ll t){//printf("%lld:\n",t);
L(i,0,d[n]-1){
ll x=i,id=0;
dp[i]=0;
while(x){
if(x%2){
ll dt=max(0ll,min(t-sum[i-d[id]],b[id]));
sum[i]=sum[i-d[id]]+a[id];
dp[i]=max(dp[i],dp[i-d[id]]+c[id][dt]);
}
x/=2;id++;
}//printf("%lld %lld\n",i,dp[i]);
if(dp[i]>=m)return 1;
}
return 0;
}
void solve(){
scanf("%lld%lld",&n,&m);
d[0]=1;
L(i,1,n)d[i]=d[i-1]*2;
L(i,0,n-1){
scanf("%lld%lld",&a[i],&b[i]);
L(j,1,b[i]){
scanf("%lld",&x);
c[i][j]=c[i][j-1]+x;
}
}
ll l=1,r=3000000;ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%lld\n",ans-1);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll T=1;
scanf("%lld",&T);
while(T--)solve();
}
1011
题意：小Q在(x,y)打车，可以在n个目的地中选择一个(xk,yk)，使得min(abs(x-xk)+abs(y-yk),wk)的值最大。多组询问。
（真的没想到真的没想到T-T）
思路：因为abs(x-xk)+abs(y-yk)的形式表示的是曼哈顿距离，不考虑wk的话就转化为了经典问题，将绝对值打开，即max(x+y-xi-yi,x-y-xi+yi,-x+y+xi-yi,-x-y+xi,yi)。记录每个目的地的xi+yi,xi-yi,-xi+yi,-xi-yi四个值，然后取最大即可。考虑加入wi的限制，先按w从小到大排序，并记录排序后每个后缀的 xi+yi,xi−yi,−xi+yi,−xi−yi 的最大值。
考虑二分，如果当前目的地为第mid个点，利用上述记录的后缀求出到点[mid,n]的距离的最大值d：如果wmid<d，说明[mid,n]的目的地对答案的贡献至少为wmid，将答案更新为wmid后二分范围压缩至[mid+1,n]；如果wmid≥d，说明[mid,n]的目的地对答案的贡献至少为d，将答案更新为d后二分范围压缩至[1,mid-1]。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N][4],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x0,x1,x2,x3,w;}q[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.w<v.w;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr[N][2];
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
void solve(){
scanf("%lld%lld",&n,&m);
L(i,1,n){
scanf("%lld%lld%lld",&x,&y,&z);
q[i]={x+y,x-y,-x+y,-x-y,z};
}
sort(q+1,q+n+1,cmp);
a[n+1][0]=a[n+1][1]=a[n+1][2]=a[n+1][3]=-inf;
R(i,n,1){
a[i][0]=max(a[i+1][0],q[i].x0);
a[i][1]=max(a[i+1][1],q[i].x1);
a[i][2]=max(a[i+1][2],q[i].x2);
a[i][3]=max(a[i+1][3],q[i].x3);
}
while(m--){
scanf("%lld%lld",&x,&y);
ll l=1,r=n;ans=0;
while(l<=r){
ll mid=(l+r)/2;
ll mx=max(-x-y+a[mid][0],max(-x+y+a[mid][1],max(x-y+a[mid][2],x+y+a[mid][3])));
if(mx<=q[mid].w){
ans=max(ans,mx);
r=mid-1;
}
else{
ans=max(ans,q[mid].w);
l=mid+1;
}
}
printf("%lld\n",ans);
}
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll T=1;
scanf("%lld",&T);
while(T--)solve();
}
1001
题意：对装备进行升级，一开始是0级。当它在第i级时，需要花费ci升级，有pi的概率升级成功（等级+1），1−pi的概率强化失败（等级-j，1≤j≤i），具体地说，有的概率降j级。求从0级升级到n级的期望花费。
（意识到是个要卷的东西（半在线卷积），但不会卷）
思路：用dp列出转移方程，设升级到i级的期望为gi，设，则
化简该式，∵
∴
∴
注意到这个结构是明显的卷积形式，且wj我们已知（离线），而则有我们递推得到（在线），是一个很明显的半在线卷积形式，用cdq分治NTT求解即可。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
ll m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,num,sum[N],mn,mx,ans;
ll lim,pos,tot,cnt,root,key,block;
ll a[N],b[N],c[N],d[N],dp[N],g0[N],g1[N],R[N];
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,mn,w;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
struct complx{
double r,i;
complx(){}
complx(double r,double i):r(r),i(i){}
complx operator+(const complx& rhs)const{return complx (r+rhs.r,i+rhs.i);}
complx operator-(const complx& rhs)const{return complx (r-rhs.r,i-rhs.i);}
complx operator*(const complx& rhs)const{return complx (r*rhs.r-i*rhs.i,i*rhs.r+r*rhs.i);}
void operator+=(const complx& rhs){r+=rhs.r,i+=rhs.i;}
void operator*=(const complx& rhs){r=r*rhs.r-i*rhs.i,i=r*rhs.i+i*rhs.r;}
void operator/=(const double& x){r/=x,i/=x;}
complx conj(){return complx(r,-i);}
};
bool cmp(qq u,qq v){
return u.x<v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
if(u.x!=v.x)return u.x>v.x;
else return u.z<v.z;
}};//shun序
pair<ll,ll>pr;
vector<ll>sv,vans;//v.assign(m,vector<ll>(n));
priority_queue<qq,vector<qq>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
set<pair<ll,ll> >::iterator it;
bitset<M>bi;
void init_ntt(ll limit){lim=1,k=0;while(lim<limit)lim*=2,k++;L(i,0,lim-1)R[i]=(R[i>>1]>>1)|((i&1)<<(k-1));}
void ntt(ll *f,ll type){
ll G=3,Gi=fksm(G,mod-2);//mod=998244353,G=3;mod=1e9+7,G=5;
L(i,0,lim-1)
if(i<R[i])swap(f[i],f[R[i]]);
for(ll mid=1;mid<lim;mid<<=1){
ll Wn=fksm(type==1?G:Gi,(mod-1)/(mid<<1));
for(ll j=0;j<lim;j+=(mid<<1)){
ll w=1;
for(ll k=0;k<mid;k++,w=(w*Wn)%mod){
ll x=f[j+k],y=w*f[j+k+mid]%mod;
f[j+k]=(x+y)%mod,
f[j+k+mid]=(x-y+mod)%mod;
}
}
}
}
void nttle(ll *f,ll *g,ll siz0,ll siz1){
init_ntt(siz0+siz1-1);
L(i,siz0,lim)f[i]=0;
L(i,siz1,lim)g[i]=0;
ntt(f,1);ntt(g,1);
L(i,0,lim-1)f[i]=(f[i]*g[i])%mod;
ntt(f,-1);
ll inv=fksm(lim,mod-2);
L(i,0,lim-1)f[i]=f[i]*inv%mod;
}
void cdq(ll l,ll r){
if(l==r){
dp[l+1]=(dp[l+1]+((dp[l]+c[l])*100)%mod*fksm(b[l],mod-2)%mod)%mod;
return;
}
ll mid=(l+r)/2;
cdq(l,mid);
ll siz0=mid-l+1,siz1=r-l+1;
L(i,l,mid)g0[i-l]=dp[i];
g1[0]=0;
L(i,1,r-l)g1[i]=a[i];
nttle(g0,g1,siz0,siz1);
L(i,mid+1,r){
dp[i+1]=(dp[i+1]-d[i]*g0[i-l]%mod+mod)%mod;
}
cdq(mid+1,r);
}
void solve(){
scanf("%lld",&n);
a[0]=sum[0]=0;
L(i,0,n)dp[i]=0;
L(i,0,n-1)scanf("%lld%lld",&b[i],&c[i]);
L(i,1,n-1)scanf("%lld",&a[i]);
L(i,1,n-1)sum[i]=sum[i-1]+a[i];
L(i,0,n-1){
d[i]=(100-b[i])*fksm(sum[i],mod-2)%mod*fksm(b[i],mod-2)%mod;
}
cdq(0,n-1);
printf("%lld\n",dp[n]);
//L(i,1,n)printf("%lld ",dp[i]);printf("\n");
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll T=1;
scanf("%lld",&T);
while(T--)solve();
}
京公网安备 11010502036488号