NOIP(怀古ing) 2017
Day1
T1 小凯的疑惑
数学题,打表找规律吧（雾
或许能用同余最短路做？
ans=a*b-a-b
#include <iostream>
#include <cstdio>
using namespace std;
long long a,b;
int main()
{
scanf("%lld%lld",&a,&b);
printf("%lld",a*b-a-b);
return 0;
}
T2 时间复杂度
大模拟没得说
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
using namespace std;
map<string,int> m;
stack<pair<int,string> >q;
stack<int> p;
int main()
{
int t;scanf("%d",&t);
while(t--)
{
while(!p.empty())p.pop();
while(!q.empty())q.pop();m.clear();
int n;string str;
scanf("%d",&n);cin>>str;
int ans=0,tot=0;
int pd=0,mark=0;
for(int i=1;i<=n;i++)
{
int xx=p.size();
ans=max(ans,xx);
// printf("ans=%d mark=%d p.size()=%d
",ans,mark,p.size());
char ch[5];scanf("%s",ch);
if(ch[0]=='F')
{
char ch[5][5];string str1;cin>>str1;
for(int j=2;j<=3;j++)scanf("%s",ch[j]);
if(pd==1)continue;
int x1=0;int x2=0;
if(ch[2][0]!='n')
for(int i=0;i<strlen(ch[2]);i++)x1=x1*10+ch[2][i]-'0';
if(ch[3][0]!='n')
for(int i=0;i<strlen(ch[3]);i++)x2=x2*10+ch[3][i]-'0';
if((ch[2][0]!='n'&&ch[3][0]!='n'&&x1<=x2)||(ch[2][0]=='n'&&ch[3][0]=='n'))
{
if(m[str1]==1)
{
printf("ERR
");pd=1;continue;
}
m[str1]=1;//printf("round 1
");
q.push(make_pair(1,str1));
}
else
{
if(ch[2][0]=='n'||(ch[2][0]!='n'&&ch[3][0]!='n'&&x1>x2))
{
if(m[str1]==1)
{
printf("ERR
");pd=1;continue;
}
m[str1]=1;mark+=1;
//printf("round 3
");
q.push(make_pair(3,str1));
}
else
{
if(m[str1]==1)
{
printf("ERR
");pd=1;continue;
}
m[str1]=1;
if(!mark)p.push(1);
//printf("round 2
");
q.push(make_pair(2,str1));
}
}
}
if(ch[0]=='E')
{
if(pd==1)continue;
if(q.empty())
{
printf("ERR
");pd=1;continue;
}
pair<int,string> x=q.top();q.pop();
// printf("x.first=%d ",x.first);cout<<"x.second="<<x.second<<endl;
m[x.second]=0;
if(mark==0&&x.first==2)
{
p.pop();
}
if(x.first==3)
{
mark--;
}
}
}
int tmp=0;
if(pd==1)continue;
if(!q.empty())
{
printf("ERR
");
}
else
{
if(str[2]=='1')
{
if(ans==0)printf("Yes
");else printf("No
");
}
else
{
int x=0;
for(int k=4;k<str.size()-1;k++)x=x*10+str[k]-'0';
if(x==ans)printf("Yes
");
else printf("No
");
}
}
}
return 0;
}
T3 逛公园
dijksta最短路+dp+判0环
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define pr pair<int,int>
#define mp make_pair
#define maxn 100100
using namespace std;
int n,m,k,p;
priority_queue<pr,vector<pr >,greater<pr > >q;
int dis1[maxn],vis1[maxn];
int fir1[maxn],nxt1[maxn*2],vv1[maxn*2],edge1[maxn*2];
int fir2[maxn],nxt2[maxn*2],vv2[maxn*2],edge2[maxn*2];
int tot1=0,tot2=0;
void add1(int u,int v,int w)
{
nxt1[++tot1]=fir1[u];
fir1[u]=tot1;
vv1[tot1]=v;
edge1[tot1]=w;
}
void add2(int u,int v,int w)
{
nxt2[++tot2]=fir2[u];
fir2[u]=tot2;
vv2[tot2]=v;
edge2[tot2]=w;
}
void dijkstra(int x)
{
memset(dis1,0x3f3f3f3f,sizeof(dis1));
memset(vis1,0,sizeof(vis1));
q.push(mp(0,x));
dis1[x]=0;
while(!q.empty())
{
pr A=q.top();q.pop();
int u=A.second;
if(vis1[u]==1)continue;
vis1[u]=1;
for(int i=fir1[u];i;i=nxt1[i])
{
int v=vv1[i];
if(dis1[v]>dis1[u]+edge1[i])
{
dis1[v]=dis1[u]+edge1[i];
q.push(mp(dis1[v],v));
}
}
}
}
int instack[maxn][55],f[maxn][55];
int dfs(int u,int rest)
{
if(instack[u][rest]==1)return -1;
int ans=0;
if(u==n)ans=1;
if(f[u][rest]!=-1)return f[u][rest]%p;
instack[u][rest]=1;
for(int i=fir2[u];i;i=nxt2[i])
{
int v=vv2[i];
if(rest<dis1[v]+edge2[i]-dis1[u])continue;
int tmp=dfs(v,rest-(dis1[v]+edge2[i]-dis1[u]));
if(tmp==-1)return -1;
ans=(ans+tmp)%p;
}
instack[u][rest]=0;
f[u][rest]=ans;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
tot1=0;tot2=0;
memset(fir1,0,sizeof(fir1));
memset(fir2,0,sizeof(fir2));
memset(f,-1,sizeof(f));
memset(instack,0,sizeof(instack));
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=1;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add1(y,x,z);
add2(x,y,z);
}
dijkstra(n);
dfs(1,k);
printf("%d
",f[1][k]);
}
return 0;
}
Day2
T1 奶酪
水题一道，直接连边+dfs或者用并查集就可以做了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define maxn 1010
ll n,h,r;
ll x[maxn],y[maxn],z[maxn];
int fir[maxn],nxt[maxn*maxn*2],vv[maxn*maxn*2];
int vis[maxn];
int below[maxn],up[maxn];
int tot1,tot2;
int tot=0;
void add(int x,int y)
{
nxt[++tot]=fir[x];
fir[x]=tot;
vv[tot]=y;
}
ll dis(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
}
void dfs(int u)
{
vis[u]=1;
for(int i=fir[u];i;i=nxt[i])
{
int v=vv[i];
if(vis[v]==1)continue;
dfs(v);
}
}
int pd=0;
int main()
{
int t=0;scanf("%d",&t);
while(t--)
{
tot=0;tot1=0;tot2=0;pd=0;
memset(fir,0,sizeof(fir));
memset(vis,0,sizeof(vis));
scanf("%lld%lld%lld",&n,&h,&r);
for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&dis(x[i],y[i],z[i],x[j],y[j],z[j])<=2*r*2*r)
{
add(i,j);
}
}
}
for(int i=1;i<=n;i++)
{
if(z[i]-r<=0)below[++tot1]=i;
if(z[i]+r>=h)up[++tot2]=i;
}
for(int i=1;i<=tot1;i++)
{
if(!vis[below[i]])dfs(below[i]);
}
for(int i=1;i<=tot2;i++)
{
if(vis[up[i]]==1)
{
printf("Yes
");pd=1;break;
}
}
if(!pd)printf("No
");
}
return 0;
}
T2 宝藏（待补）update于2019.8.22
题意：
有n个深埋在地下的宝藏屋，它们之间有m条道路，每条道路有一定的长度v，可以免费开通地面到任意一个宝藏物的道路，之后开发每条道路的代价是：
L×K
L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
求工程最小的总代价。
数据范围：对于100%的数据： 1<=n<=12 0<=m<=1000 v<=500000
经过观察，发现n极小，考虑状压dp
由于该条道路之前的宝藏屋数量影响答案，将其计入一维
所以dp方程为：设f[i][j]表示已开发的宝藏屋状态为i，下一批开发的道路之前的宝藏屋数量为j的最小代价。
然后因为每个集合S一定由之前的集合S0转移得到，又n<=12，故可以枚举子集
复杂度：O（n2*3n），再加上一些判断这个复杂度是可以过的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int dis[20][20];
int g[1<<15];
int f[1<<15][15];
int main()
{
scanf("%d%d",&n,&m);
memset(f,0x3f3f3f3f,sizeof(f));
memset(dis,0x3f3f3f3f,sizeof(dis));
for(int i=1;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
dis[x][y]=dis[y][x]=min(dis[x][y],z);
}
for(int i=1;i<=(1<<n)-1;i++)
{
for(int j=1;j<=n;j++)
{
if(((1<<(j-1))&i)!=0)
{
dis[j][j]=0;
for(int k=1;k<=n;k++)
{
if(dis[j][k]<1e9)
{
g[i]|=(1<<(k-1));
}
}
}
}
}
for(int i=1;i<=n;i++)f[1<<(i-1)][1]=0;
for(int s=1;s<=(1<<n)-1;s++)//
{
for(int s0=s;s0;s0=(s0-1)&s)//
{
if((g[s0]|s)==g[s0])//
{
int sum=0;
int ss=s0^s;
for(int k=1;k<=n;k++)//
{
if(((1<<(k-1))&ss)!=0)
{
int tmp=1e9;
for(int t=1;t<=n;t++)//
{
if((((1<<(t-1))&s0)!=0)&&dis[t][k]<1e9)
{
tmp=min(tmp,dis[t][k]);
}
}
sum+=tmp;
}
}
for(int j=2;j<=n;j++)if(f[s0][j-1]<1e9)
{
f[s][j]=min(f[s][j],f[s0][j-1]+sum*(j-1));
}
}
}
}
int ans=1e9;
for(int i=1;i<=n;i++)ans=min(ans,f[(1<<n)-1][i]);
printf("%d
",ans);
return 0;
}
T3 列队（待补）