长乐集训 Day9
LimpidSlirm · · 个人记录
A.kobe
题意
Solution
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!('0'<=ch&&ch<='9')) (ch=='-')?flag=-1:1,ch=getchar();
while('0'<=ch&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*flag;
}
int a[100],b[100];
int dp[100][1610];
int main(int argc,const char *argv[])
{
freopen("kobe.in","r",stdin);
freopen("kobe.out","w",stdout);
int n=read(),sum=0;
for(int i=1;i<=n;i++)
a[i]=read(),sum+=a[i];
for(int i=1;i<=n;i++)
b[i]=read();
memset(dp,128,sizeof dp);
//cout<<dp[0][0];
dp[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=i;j>=1;j--)
for(int k=b[i];k<=1600;k++)
dp[j][k]=std::max(dp[j][k],dp[j-1][k-b[i]]+a[i]);
for(int i=1;i<=n;i++)
for(int j=1600;j>=0;j--)
dp[i][j]=std::max(dp[i][j],dp[i][j+1]);
int q=read();
for(int i=1;i<=q;i++)
{
int k=read();
if(k<n)
printf("%d\n",dp[k][sum]<0?-1:sum-dp[k][sum]);
if(k==n)
printf("0\n");
if(k>n)
printf("-1\n");
}
return 0;
}
B.habibi
题意
Solution
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!('0'<=ch&&ch<='9')) (ch=='-')?flag=-1:1,ch=getchar();
while('0'<=ch&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*flag;
}
struct edge
{
int to,nxt;
};
int n,m,q,tot;
bool check[30][30];
int val[200010];
int head[200010];
int las[200010][30];
int query[2000010];
struct edge ed[400010];
void add_edge(int fr,int to)
{
ed[++tot]=(edge){to,head[fr]};
head[fr]=tot;
return ;
}
void init(int fr,int fa)
{
for(int i=1;i<=m;i++)
{
if(check[i][val[fr]]==true)
las[fr][i]=las[fa][i];
else
las[fr][i]=fr;
}
for(int i=head[fr];i!=0;i=ed[i].nxt)
{
if(ed[i].to==fa)
continue;
init(ed[i].to,fr);
}
return ;
}
int main(int argc,const char *argv[])
{
freopen("habibi.in","r",stdin);
freopen("habibi.out","w",stdout);
n=read(),m=read(),q=read();
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
check[i][j]=read();
for(int i=1;i<=n;i++)
val[i]=read();
for(int i=1;i<n;i++)
{
int fr=read(),to=read();
add_edge(fr,to);
add_edge(to,fr);
}
init(1,0);
for(int i=1;i<=q;i++)
{
int k=read(),pos=read();
for(int j=1;j<=k;j++)
query[j]=read();
for(int j=k;j>=1;j--)
{
pos=las[pos][query[j]];
if(pos==0)
break;
}
putchar(pos==0?'1':'0');
putchar('\n');
}
return 0;
}
C.escape
题意
Solution
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!('0'<=ch&&ch<='9')) (ch=='-')?flag=-1:1,ch=getchar();
while('0'<=ch&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*flag;
}
const long long mod=998244353;
const long long inv=499122177;
#define mod(a) a>mod?a-mod:a
struct edge
{
int to,nxt;
};
int n,k,tot;
int head[5010],val[5010];
int dp[5010][5010];
struct edge ed[10010];
void add_edge(int fr,int to)
{
ed[++tot]=(edge){to,head[fr]};
head[fr]=tot;
return ;
}
long long quick(long long a,long long b)
{
long long res=1;
while(b!=0)
{
if(b&1==true)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void solve(int fr,int fa)
{
for(int i=head[fr];i!=0;i=ed[i].nxt)
{
int to=ed[i].to;
if(to==fa)
continue;
for(int j=val[to];j<=k;j++)
dp[to][j]=1ll*dp[fr][j-val[to]]*inv%mod;
solve(to,fr);
for(int j=0;j<=k;j++)
dp[fr][j]=mod(1ll*dp[fr][j]*inv%mod+dp[to][j]%mod);
}
return ;
}
int main(int argc,const char *argv[])
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++)
val[i]=read();
for(int i=1;i<n;i++)
{
int fr=read(),to=read();
add_edge(fr,to);
add_edge(to,fr);
}
dp[1][val[1]]=val[1]<=k?1:0;
solve(1,0);
printf("%lld",dp[1][k]);
return 0;
}D.kaoyapp
题意
Solution
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!('0'<=ch&&ch<='9')) (ch=='-')?flag=-1:1,ch=getchar();
while('0'<=ch&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*flag;
}
inline string Read()
{
string res="";
char ch=getchar();
while(!('0'<=ch&&ch<='9'))
ch=getchar();
while('0'<=ch&&ch<='9')
res=res+ch,ch=getchar();
return res;
}
struct node
{
bool end;
int son[10];
};
int tot=1,root=1;
int fa[8000010];
struct node nd[8000010];
char s[8000010],t[8000010];
int get(int x)
{
if(fa[x]==x)
return x;
return fa[x]=get(fa[x]);
}
void insert()
{
int pos=root;
for(int i=0;i<strlen(s);i++)
{
int &nxt=nd[pos].son[s[i]-'0'];
if(nxt==0)
nxt=++tot,fa[tot]=tot;
//cerr<<"insert:"<<pos<<" "<<s[i]-'0'<<" "<<get(nxt)<<endl;
pos=get(nxt);
}
nd[pos].end=true;
return ;
}
bool query()
{
int pos=root;
for(int i=0;i<strlen(s);i++)
{
if(pos==0)
return false;
pos=get(nd[pos].son[s[i]-'0']);
}
return nd[pos].end;
}
int find(char *s)
{
int pos=root;
for(int i=0;i<strlen(s);i++)
{
int &nxt=nd[pos].son[s[i]-'0'];
if(nxt==0)
nxt=++tot,fa[tot]=tot;
pos=get(nxt);
}
return pos;
}
void merge(int &a,int &b,bool flag)
{
a=get(a),b=get(b);
//cerr<<a<<" "<<b<<endl;
if(a==b)
return ;
fa[b]=a;
nd[a].end|=nd[b].end;
for(int i=0;i<=9;i++)
{
if(nd[a].son[i]==0||nd[b].son[i]==0)
{
nd[a].son[i]=nd[a].son[i]+nd[b].son[i];
continue ;
}
merge(nd[a].son[i],nd[b].son[i],false);
a=get(a);
}
return ;
}
int main(int argc,const char *argv[])
{
freopen("kaoyapp.in","r",stdin);
freopen("kaoyapp.out","w",stdout);
int q=read();
fa[1]=1;
for(int i=1;i<=q;i++)
{
int opt=read();
scanf("%s",s);
if(opt==1)
insert();
if(opt==2)
putchar(query()?'1':'0'),putchar('\n');
if(opt==3)
{
scanf("%s",t);
int a=find(s);
int b=find(t);
// cerr<<"solve"<<a<<" "<<b<<endl;
merge(a,b,true);
}
}
return 0;
}