CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Brainwashing Device
#include<bits/stdc++.h>
using namespace std;
const int N=511,INF=1e9;
int n,K,f[N][N],a[N][N],c[N][N],s[N][N],g[N][N];
int main()
{
scanf("%d%d",&n,&K);
for(int i=1,t; i<=n; ++i)
for(int j=i+1; j<=n; ++j)
{
scanf("%d",&a[i][j]);
}
for (int i=1; i<=n; i++)
for (int j=i+1; j<=n; j++)
for (int k=1; k<=i; k++)
c[i][j]+=a[k][j];
for (int i=1;i<=n;i++)
for (int j=i+1; j<=n;j++)
for (int k=i+1;k<=j;k++)
s[i][j]+=c[i][k];
for (int i=1;i<=n;i++) f[i][1]=s[i][n];
for (int i=2; i<=K;i++)
for (int j=1;j<=n;j++)
for (int k=j+1;k<=n;k++)
{
if (s[j][k]+f[k][i-1]>f[j][i]) f[j][i]=s[j][k]+f[k][i-1],g[j][i]=k;
}
int ans=0,ansnum;
for (int i=1;i<=n;i++)
if (f[i][K]>ans) ans=f[i][K],ansnum=i;
printf("%d\n",ans);
printf("%d ",ansnum);
while (K>1)
{
printf("%d ",g[ansnum][K]);
ansnum=g[ansnum][K];
K--;
}
}
Space Elevators
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=100000+10;
int n,s,cnt,num,l,r;
int v[maxn],ans[maxn];
queue <int> q;
int main()
{
scanf("%d%d",&n,&s);
for (int i=1;i<=n;i++) scanf("%d",&v[i]);
sort(v+1,v+n+1);
cnt=num=0; l=1; r=n;
while (l<=r)
{
if (q.empty())
{
q.push(v[l++]);
// printf("%d %d\n",l,r);
continue;
}
if (q.front()+v[r]>s)
{
ans[++cnt]=q.front();
q.pop();
ans[++cnt]=v[r];
r--;
num+=2;
}
else
{
ans[++cnt]=q.front();
q.pop();
ans[++cnt]=v[l++];
num++;
}
}
if (!q.empty()) ans[++cnt]=q.front(),num++;
printf("%d\n",num);
for (int i=1;i<=cnt;i++) printf("%d ",ans[i]);
return 0;
}
Neo-Venice
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,t,s;
int a[200];
int main()
{
scanf("%d%d%d",&n,&t,&s);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<=n;++i)
{
int del=a[i]-s;
double ans=double(t-del);
ans=ans/2+del+s;
printf("%.6lf\n",ans);
}
return 0;
}
Unidentified Ships
#include<bits/stdc++.h>
#define inv(a,b) pow(a,(b)-2,b)
#define mul(a,b,c) (1LL*(a)*(b)%(c))
using namespace std;
typedef int ll;
const int N=8191,M=1e9+7;
ll pow(ll a,ll b,ll m)
{
ll r=1;
for(a%=m; b; b>>=1,a=mul(a,a,m))
if(b&1)r=mul(r,a,m);
return r;
}
struct Factorial
{
vector<ll> fac,ifac;
ll M;
Factorial(int N,ll M):fac(N,1),ifac(N,1),M(M)
{
for(int i=1; i<N; ++i)fac[i]=mul(fac[i-1],i,M);
ifac[N-1]=inv(fac[N-1],M);
for(int i=N-1; i; --i)ifac[i-1]=mul(ifac[i],i,M);
}
ll c(int n,int m)
{
return mul(mul(fac[n],ifac[m],M),ifac[n-m],M);
}
} f(N,M);
int n,t,c[N],k,x,s[3];
int main()
{
scanf("%d%d",&n,&t);
for(int i=0; i<n; ++i)scanf("%d",&c[i]);
scanf("%d%d",&k,&x);
for(int i=0; i<n; ++i)++s[c[i]>c[k-1]?2:c[i]==c[k-1]];
for(int i=min(s[k=0],x-1); ~i; --i)
for(int j=min(s[2],t-x); ~j; --j)
if(1<=t-i-j&&t-i-j<=s[1])
k=(k+mul(mul(f.c(s[0],i),f.c(s[2],j),M),f.c(s[1]-1,t-i-j-1),M))%M;
printf("%d\n",k);
}
The Lessons of the Past
using namespace std;
const int N=10009;
int k,a[15],c[N*2];
int check(int t)
{
for(int i=0; i<k; ++i)
t=abs(t-a[i]);
return t<=1;
}
int main()
{
scanf("%d",&k);
for(int i=0; i<k; ++i)scanf("%d",&a[i]);
vector<pair<int,int> > ans;
for(int i=-N,l=N; i<N; ++i)
if(check(i))
{
if(l==N)l=i;
if(!check(i+1))
{
ans.push_back(make_pair(l,i));
l=N;
}
}
printf("%d\n",ans.size());
for(int i=0; i<ans.size(); ++i)
printf("%d %d\n",ans[i].first,ans[i].second);
}
Travel in Time
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef int ll;
const int N=1e5+9,NPOS=-1;
pair<pair<int,int>,pair<int,int> > P[N];
vector<int> V[N];
int q[N],cur[N],p[N],n,m,s,t,st,tt;
bool cmp(int i,int j)
{
return P[i]<P[j];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<m; ++i)
scanf("%d%d%d%d",&P[i].S.F,&P[i].S.S,&P[i].F.F,&P[i].F.S);
for(int i=m; i<m+2; ++i)scanf("%d",&P[i].S.F),P[i].S.S=P[i].S.F;
for(int i=m; i<m+2; ++i)scanf("%d",&P[i].F.F),P[i].F.S=P[i].F.F;
for(int i=0; i<m+2; ++i)
V[P[i].S.F].push_back(i);
for(int i=1; i<=n; ++i)sort(V[i].begin(),V[i].end(),cmp),cur[i]=V[i].size()-1;
fill(p,p+m+2,NPOS);
q[0]=m;
for(int ql=0,qr=1; ql<qr; ++ql)
for(int &u=q[ql],&j=cur[P[u].S.S],to; ~j; --j)
if(to=V[P[u].S.S][j],to!=u)
{
if(P[u].F.S>P[to].F.F)break;
if(p[to]==NPOS)p[to]=u,q[qr++]=to;
}
if(p[m+1]==NPOS)return printf("Impossible"),0;
vector<int> ans;
for(int u=m+1; u!=m; u=p[u])
ans.push_back(u);
printf("%d\n",ans.size()-1);
for(int i=ans.size()-1; i; --i)
printf("%d ",ans[i]+1);
}
The Lost Civilization
//没人做的题，待补
Coffee and Buns
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,at,n,ans;
int cnt;
ll f[100];
void dfs1(int cur,int num,ll tot)
{
if (tot>n) return ;
if (cur>cnt)
{
if (num==0) return ;
ans+=(num&1?1:-1)*(n/tot);
return ;
}
dfs1(cur+1,num,tot);
dfs1(cur+1,num+1,tot*f[cur]);
}
void dfs2(int cur,int num,ll tot)
{
if (cur>cnt)
{
if (num==0) return ;
ans+=(num&1?1:-1)*(((n/tot)+1)/2);
// printf("%d %d\n",tot,ans);
return ;
}
dfs2(cur+1,num,tot);
dfs2(cur+1,num+1,tot*f[cur]);
}
int main()
{
scanf("%lld%lld",&a,&n);
at=a;
for (int i=2;(ll)i*i<=a;i++)
if (at%i==0)
{
f[++cnt]=i;
while (at%i==0) at/=i;
}
if (at>1) f[++cnt]=at;
if (a&1)
{
ans+=(n+1)/2;
n/=2;
dfs1(1,0,1);
}
else
{
ans+=n/2;
dfs2(2,0,1);
}
printf("%lld",ans);
return 0;
}
Brute-force Search
//待补
Space Recon
//全场193提交无人通过，待补
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
double X0,X1,X2,Y0,Y1,Y2,z0,z1,z2,vx,vy,vz,r;
double A,B,C,D;
const double eps=1e-6;
void getN()
{
double dx=X1-X2,dy=Y1-Y2,dz=z1-z2;
A=dy*vz-dz*vy;
B=dz*vx-dx*vz;
C=dx*vy-dy*vx;
D=-X1*A-Y1*B-z1*C;
}
bool dir()
{
double Dx=X1-X0,Dy=Y1-Y0,Dz=z1-z0;
if (Dx*vx+Dy*vy+Dz*vz<eps) return true;
Dx=X2-X0,Dy=Y2-Y0,Dz=z2-z0;
if (Dx*vx+Dy*vy+Dz*vz<eps) return true;
return false;
}
double DD(double x,double y,double z)
{
double dx=X0-x,dy=Y0-y,dz=z0-z;
double L1=(dx*vx+dy*vy+dz*vz)/sqrt(vx*vx+vy*vy+vz*vz);
double L2=(dx*dx+dy*dy+dz*dz)-L1*L1;
if (L2-r*r>-eps) return -1;
double L3=sqrt(r*r-L2);
return L1-L3;
}
int main()
{
// freopen("J.txt","r",stdin);
scanf("%lf%lf%lf%lf",&X0,&Y0,&z0,&r);
scanf("%lf%lf%lf",&X1,&Y1,&z1);
scanf("%lf%lf%lf",&X2,&Y2,&z2);
scanf("%lf%lf%lf",&vx,&vy,&vz);
getN();
double dis=(A*X0+B*Y0+C*z0+D)/sqrt(A*A+B*B+C*C);
if (dis-r>eps) {printf("False alarm");return 0;}
if (!dir()) {printf("False alarm");return 0;}
double d1=DD(X1,Y1,z1);
double d2=DD(X2,Y2,z2);
double d3;
if (d1<-eps && d2<-eps) {printf("Warning");return 0;}
if (d1<-eps || d2<-eps) d3=max(d1,d2);
else d3=min(d1,d2);
double T=d3/sqrt(vx*vx+vy*vy+vz*vz);
X1+=vx*T;Y1+=vy*T;z1+=vz*T;
X2+=vx*T;Y2+=vy*T;z2+=vz*T;
double Px=X1-X2,Py=Y1-Y2,Pz=z1-z2;
double Qx=X0-X2,Qy=Y0-Y2,Qz=z0-z2;
double Rx=X0-X1,Ry=Y0-Y1,Rz=z0-z1;
if (Px*Qx+Py*Qy+Pz*Qz>-eps || Rx*Px+Ry*Py+Rz*Pz<eps) {printf("Crash");return 0;}
double k=((X1-X2)*(X0-X2)+(Y1-Y2)*(Y0-Y2)+(z1-z2)*(z0-z2))/((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)+(z1-z2)*(z1-z2));
double d4=sqrt(((X1-X2)*k+X2-X0)*((X1-X2)*k+X2-X0)+((Y1-Y2)*k+Y2-Y0)*((Y1-Y2)*k+Y2-Y0)+((z1-z2)*k+z2-z0)*((z1-z2)*k+z2-z0));
if (d4-r<eps) {printf("Warning");return 0;}
else {printf("Crash");return 0;}
}