chinaxjh

none

chinaxjh
21天前

#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int N=20003;
const int M=203;
int n,m,i,ss,tt,ww,cc,ee,qq,len,a[N],b[N],las[N],nxt[N],p[N],ans[N][M];
bool vis[N][M];
struct node
{
int u,f,w;
node(int x,int y,int z):u(x),f(y),w(z) {}
friend bool operator < (node a,node b)
{
return a.w>b.w;
}
};
priority_queue <node> q;
{
len++;
a[len]=t;
b[len]=w;
nxt[len]=las[s];
las[s]=len;
}

{
int x,y,i;
while (!q.empty()) q.pop();
q.push(node(s,0,0));
ans[s][0]=0;

while (!q.empty())
{
x=q.top().u;
y=q.top().f;
q.pop();
vis[x][y]=true;
if (x==e)
{
printf("%d\n",ans[x][y]);
return;
}
if (y<c)
if (!vis[x][y+1])
if (ans[x][y]+p[x]<ans[x][y+1])
{
ans[x][y+1]=ans[x][y]+p[x];
q.push(node(x,y+1,ans[x][y+1]));
}
for (i=las[x];i;i=nxt[i])
if (y-b[i]>=0)
{
if (vis[a[i]][y-b[i]]) continue;
if (ans[x][y]<ans[a[i]][y-b[i]])
{
ans[a[i]][y-b[i]]=ans[x][y];
q.push(node(a[i],y-b[i],ans[a[i]][y-b[i]]));
}
}

}
puts("impossible");
}
int main()
{
cin>>n>>m;
fori(i,1,n)
scanf("%d",&p[i]);
fori(i,1,n)
{
scanf("%d%d%d",&ss,&tt,&ww);
}
cin>>qq;
fori(i,1,qq)
{
scanf("%d%d%d",&cc,&ss,&ee);
memset(ans,0x3f,sizeof(ans));
memset(vis,false,sizeof(vis));
}
}


chinaxjh
2个月前
#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
int m,w,i,k,n,ans,c[1000],a[1000];
void search(int k,int num)
{
int i;
if (num>=ans) return;
if (k>n)
{
ans=min(ans,num);
return;
}
fori(i,1,num)
if (a[i]+c[k]<=w)
{
a[i]+=c[k];
search(k+1,num);
a[i]-=c[k];
}
num++;
a[num]=c[k];
search(k+1,num);
}
int main()
{
cin>>n>>w;
fori(i,1,n)
cin>>c[i];
sort(c+1,c+1+n);
reverse(c+1,c+1+n);
ans=10000;
search(1,0);
cout<<ans<<endl;
}


chinaxjh
3个月前
#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int N=1e6+5;
const ull base=10007;
char s[N];
ull sum1[N],sum2[N],pows[N];
int ans,i,len,testcase;
ull gethashz(int x,int y)
{
return sum1[y]-sum1[x-1]*pows[y-x+1];
}
ull gethashf(int x,int y)
{
return sum2[x]-sum2[y+1]*pows[y-x+1];
}
int ji(int x)
{
int l,r,bo;
bo=0;
l=(ans-1)/2+1;
r=min(x-1,len-x);
while (l<=r)
{
int mid;
mid=(l+r)/2;
if (gethashz(x-mid,x-1)==gethashf(x+1,x+mid))
{
bo=mid;
l=mid+1;
} else r=mid-1;
}
return bo*2+1;
}
int ou(int x)
{
int l,r,bo;
bo=0;
l=ans/2+1;
r=min(x,len-x);
while (l<=r)
{
int mid;
mid=(l+r)/2;
if (gethashz(x-mid+1,x)==gethashf(x+1,x+mid))
{
bo=mid;
l=mid+1;
} else r=mid-1;
}
return bo*2;
}
int main()
{
pows[0]=1;
fori(i,1,1e6)
pows[i]=pows[i-1]*base;
while (++testcase)
{
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
scanf("%s",s+1);
ans=1;
if (s[1]=='E'&&s[2]=='N'&&s[3]=='D') break;
len=strlen(s+1);
fori(i,1,len)
sum1[i]=sum1[i-1]*base+(ull)(s[i]-'a'+1);
ford(i,len,1)
sum2[i]=sum2[i+1]*base+(ull)(s[i]-'a'+1);
fori(i,1,len)
ans=max(ans,ji(i));
fori(i,1,len-1)
if (s[i]=s[i+1]) ans=max(ans,ou(i));
cout<<"Case "<<testcase<<": "<<ans<<endl;
}
}


chinaxjh
3个月前
#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int Mod=1145141;
const int N=100005;
ll bo,n,j,i,t,m,las[Mod+5],a[N][8],b[N],nxt[N],c[8];
bool pd(ll x,ll y)
{
ll i,j,k,t,boo;
fori(i,1,6)
{
j=i;
t=1;
c[t]=a[x][j];
j++;
if (j>6) j=1;
while (j!=i)
{
t++;
c[t]=a[x][j];
j++;
if (j>6) j=1;
}
boo=true;
for (j=1;j<=6;j++)
if (a[y][j]!=c[j]) boo=false;
if (boo) return true;
}
fori(i,1,6)
{
j=i;
t=1;
c[t]=a[x][j];
j--;
if (j==0) j=6;
while (j!=i)
{
t++;
c[t]=a[x][j];
j--;
if (j==0) j=6;
}
boo=true;
for (j=1;j<=6;j++)
if (a[y][j]!=c[j]) boo=false;
if (boo) return true;
}
return false;
}
ll gethash(ll i)
{
ll j,ans,jia,cheng;
cheng=1;
jia=0;
fori(j,1,6)
jia=(jia+a[i][j])%Mod,
cheng=cheng*a[i][j]%Mod;
ans=(jia+cheng)%Mod;
}
int main()
{
cin>>n;
fori(j,1,6)
scanf("%lld",&a[1][j]);
t=gethash(1);
m++;
las[t]=m;
b[m]=1;
fori(i,2,n)
{
fori(j,1,6)
scanf("%lld",&a[i][j]);
t=gethash(i);
if (las[t]==0)
{
m++;
las[t]=m;
b[m]=i;
} else {
bo=true;
for (j=las[t];j;j=nxt[j])
if (pd(i,b[j]))
{
puts("Twin snowflakes found.");
return 0;
}
if (bo)
{
m++;
b[m]=i;
nxt[las[t]]=m;
las[t]=m;

}
}
}
puts("No two snowflakes are alike.");
}


chinaxjh
3个月前
#include<bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int base=1145141;
const int N=1000000+5;
char s[N];
int x1,x2,yy1,yy2;
ull i,len,n,pows[N],sum[N];
ull gethash(int x,int y)
{
return (ull)(sum[y]-sum[x-1]*pows[y-x+1]);
}
int main()
{
cin>>s+1;
len=strlen(s+1);
pows[0]=1;
for (i=1;i<=len;i++)
pows[i]=pows[i-1]*base;
for (i=1;i<=len;i++)
sum[i]=sum[i-1]*base+(ull)(s[i]-'a'+1);
cin>>n;
while (n--)
{
scanf("%d%d%d%d",&x1,&yy1,&x2,&yy2);
if (gethash(x1,yy1)==gethash(x2,yy2)) puts("Yes");
else puts("No");
}
}


chinaxjh
4个月前
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=32;
int n,i,a[6];
ll f[N][N][N][N][N];
int main()
{
while (1)
{
cin>>n;
if (n==0) break;
memset(a,0,sizeof(a));
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(f,0,sizeof(f));
f[0][0][0][0][0]=1;

for (int a1=0;a1<=a[1];a1++)
for (int a2=0;a2<=min(a1,a[2]);a2++)
for (int a3=0;a3<=min(a2,a[3]);a3++)
for (int a4=0;a4<=min(a3,a[4]);a4++)
for (int a5=0;a5<=min(a4,a[5]);a5++)
{
if (a1!=a[1])
f[a1+1][a2][a3][a4][a5]+=f[a1][a2][a3][a4][a5];
if (a2!=a[2])
f[a1][a2+1][a3][a4][a5]+=f[a1][a2][a3][a4][a5];
if (a3!=a[3])
f[a1][a2][a3+1][a4][a5]+=f[a1][a2][a3][a4][a5];
if (a4!=a[4])
f[a1][a2][a3][a4+1][a5]+=f[a1][a2][a3][a4][a5];
if (a5!=a[5])
f[a1][a2][a3][a4][a5+1]+=f[a1][a2][a3][a4][a5];
}
cout<<f[a[1]][a[2]][a[3]][a[4]][a[5]]<<endl;
}
}



chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=4003;
long long f[N];
int n,i,j;
int main()
{
cin>>n;
f[0]=1;
for (i=1;i<n;i++)
for (j=i;j<=n;j++)
f[j]=(f[j-i]+f[j])%2147483648;
cout<<f[n]<<endl;
}


chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=2003;
const int inf=1e9;
int a[N],b[N],f[N][N];
int n,i,j,anss,ans,ansd;
int main()
{
cin>>n;
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
for (i=1;i<=n;i++)
{
anss=inf;
for (j=1;j<=n;j++)
{
anss=min(anss,f[i-1][j]);
f[i][j]=anss+abs(a[i]-b[j]);
}
}
ans=inf;
for (i=1;i<=n;i++) ans=min(ans,f[n][i]);
reverse(b+1, b+1+n);
for (i=1;i<=n;i++)
{
anss=inf;
for (j=1;j<=n;j++)
{
anss=min(anss,f[i-1][j]);
f[i][j]=anss+abs(a[i]-b[j]);
}
}
ansd=inf;
for (i=1;i<=n;i++) ansd=min(ansd,f[n][i]);
cout<<min(ans,ansd)<<endl;
}


chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
int n,m,i,k,j,t,f[50][50][50][50],a[1000],b[1000];
int main()
{
cin>>n>>m;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=m;i++)
{
scanf("%d",&k);
b[k]++;
}
for (i=0;i<=b[1];i++)
for (j=0;j<=b[2];j++)
for (k=0;k<=b[3];k++)
for (t=0;t<=b[4];t++)
{
if (i!=0) f[i][j][k][t]=max(f[i-1][j][k][t],f[i][j][k][t]);
if (j!=0) f[i][j][k][t]=max(f[i][j-1][k][t],f[i][j][k][t]);
if (k!=0) f[i][j][k][t]=max(f[i][j][k-1][t],f[i][j][k][t]);
if (t!=0) f[i][j][k][t]=max(f[i][j][k][t-1],f[i][j][k][t]);
f[i][j][k][t]=f[i][j][k][t]+a[1+i+2*j+3*k+4*t];
}
cout<<f[b[1]][b[2]][b[3]][b[4]]<<endl;
}


chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int a[N],b[N],f[N][N],i,j,n,m,val,ans;
int main()
{
cin>>n;
m=n;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=m;i++) scanf("%d",&b[i]);
for (i=1;i<=n;i++)
{
val=0;
if (b[0]<a[i]) val=f[i-1][0];
for (j=1;j<=m;j++)
{
if (a[i]==b[j]) f[i][j]=val+1;
else f[i][j]=f[i-1][j];
if (b[j]<a[i]) val=max(val,f[i-1][j]);
}
}
for (j=1;j<=m;j++) ans=max(ans,f[n][j]);
cout<<ans<<endl;
}