如果这篇博客帮助到你,可以请我喝一杯咖啡~
CC BY 4.0 (除特别声明或转载文章外)
An Olympian Math Problem
#include<stdio.h>
int main()
{
long long t,n;
for(scanf("%lld",&t); t--; printf("%lld\n",n-1))
scanf("%lld",&n);
}
AC Challenge
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=25;
const int maxv=1<<22;
const long long inf=-100000000000000;
queue <long long> q[2];
long long f[2][maxv];
bool inq[maxv];
int pre[maxn];
int val[maxn][maxn];
int n,a,b,s,u,V;
long long ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
for (int j=1;j<=n;j++) val[i][j]=a*j+b;
scanf("%d",&s);
for (int j=1;j<=s;j++)
{
scanf("%d",&u);
pre[i]+=1<<u;
}
}
V=1<<n+1;
for (int i=1;i<=n;i++)
if (pre[i]==0) f[1][1<<i]=val[i][1],q[1].push(1<<i);
for (int i=2;i<=n;i++)
{
memset(inq,false,sizeof(inq));
while (!q[(i+1)%2].empty())
{
int g=q[(i+1)%2].front();
//printf("%d %d\n",i,g);
q[(i+1)%2].pop();
for (int j=1;j<=n;j++)
{
if ((1<<j)&g) continue;
if ((g&pre[j])!=pre[j]) continue;
// if (f[(i+1)%2][k]+val[j][i]>f[i%2][k+(1<<j)]) printf("%d %d %d\n",j,k,f[(i+1)%2][k]+val[j][i]);
int nxt=g+(1<<j);
if (f[(i+1)%2][g]+val[j][i]>f[i%2][nxt])
{
f[i%2][nxt]=f[(i+1)%2][g]+val[j][i];
if (!inq[nxt]) q[i%2].push(nxt),inq[nxt]=true;
ans=max(ans,f[i%2][nxt]);
}
}
f[(i+1)%2][g]=inf;
}
}
printf("%lld",ans);
return 0;
}
Sum
线性筛处理一下。
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e7+7;
struct EulerSieve
{
vector<int> p,m,f;
EulerSieve(int N):m(N,0),f(N)
{
f[1]=1;
for(long long i=2,k; i<N; ++i)
{
if(!m[i])p.push_back(m[i]=i),f[i]=2;
for(int j=0; j<p.size()&&(k=i*p[j])<N; ++j)
if(f[k]=f[i]*2,(m[k]=p[j])==m[i])
{
f[k]/=4;
break;
}
}
for(int i=0,p3; p3=p[i]*p[i]*p[i],p3<N; ++i)
for(int j=p3; j<N; j+=p3)
f[j]=0;
}
} e(N);
long long sum[N];
int t,n;
int main()
{
for(int i=1; i<N; ++i)sum[i]=sum[i-1]+e.f[i];
for(scanf("%d",&t); t--; printf("%lld\n",sum[n]))
scanf("%d",&n);
}
Magical Girl Haze
居然有 spfa 过的…
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int N=12e5,NPOS=-1;
struct Edge
{
int from,to;
ll dist;
} e[N<<2];
int ea[N<<2],va[N],es,vs;
void init(int n)
{
fill(va,va+(vs=n),NPOS);
es=0;
}
void add(const Edge &ed)
{
ea[es]=va[ed.from];
va[ed.from]=es;
e[es++]=ed;
}
ll d[N];
void ask(int s)
{
fill(d,d+vs,INF);
priority_queue<pair<ll,int> > q;
for(q.push(make_pair(d[s]=0,s)); !q.empty();)
{
ll dis=-q.top().first;
int u=q.top().second;
if(q.pop(),d[u]<dis)continue;
for(int k=va[u],to; k!=NPOS; k=ea[k])
if(to=e[k].to,d[to]>d[u]+e[k].dist)
{
d[to]=d[u]+e[k].dist;
q.push(make_pair(-d[to],to));
}
}
}
int main()
{
int t,n,m,k;
for(scanf("%d",&t); t--;)
{
scanf("%d%d%d",&n,&m,&k);
init(n*(k+2));
for(int i=0,u,v,c; i<m; ++i)
{
scanf("%d%d%d",&u,&v,&c),--u,--v;
for(int j=0; j<=k; ++j)
add({u+j*n,v+j*n,c}),add({u+j*n,v+(j+1)*n,0});
}
ask(0);
printf("%lld\n",d[n*(k+1)-1]);
}
}