【比赛报告】NOIP2017真题 NOIP练习赛卷十一
小凯的疑惑
来了，传说中的 ……一道玄学的结论题（我也不会证）
#include<cstdio>
typedef unsigned long long ull;
int main()
{
ull a,b;
scanf("%llu%llu",&a,&b);
printf("%llu\n",a*b-a-b);
return 0;
}
总结
玄学数论……说不定今年也来一道
时间复杂度
星际玩家不需要注意大小写……我提交七八遍没看出来自己大小写错了
大佬题解写得贼简洁，一看就是神仙，赶紧学习了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t,len,F,e,k,maxn,g[110],h,l[110],n,f[110];
string a,b;
int main()
{
//freopen("in.txt","r",stdin);
cin>>t;
while(t--)
{
len=0,F=0,e=0,k=0,maxn=0,memset(g,0,sizeof(g)),h=0,memset(l,0,sizeof(l)),n=0,memset(f,0,sizeof(f));
do{
a=b;cin>>b;
}while(b[0]!='O');
for(int i=0;i<a.length();i++)len=len*10+a[i]-'0';//长度
for(int i=4;i<b.length()-1;i++)F=F*10+b[i]-'0';
while(len>0)
{
cin>>a;len--;
if(a[0]=='F')
{
cin>>a;e++;
if(f[a[0]-96])e=-1;
else f[a[0]-96]=1,g[e]=a[0]-96;//记一下e层循环的变量
cin>>a>>b;//初始值和结束值
if(a[0]!='n'&&b[0]=='n'&&k==0)h++,l[e]=1;
else if(((a.length()>b.length())||(a.length()==b.length()&&a>b)||(a[0]=='n'&&b[0]!='n'))&&k==0)k=1,n=e;//从n开始不能运行了
}
else
{
maxn=max(maxn,h);f[g[e]]=0;
if(l[e]==1)h--,l[e]=0;
e--;
if(n>0&&e<n)k=0,n=0;
}
if(e==-1){printf("ERR\n");len=-1;}
}
if(e>0)printf("ERR\n");
if(e==0&&maxn==F)printf("Yes\n");
if(e==0&&maxn!=F)printf("No\n");
}
return 0;
}
总结
能把大模拟写这么简介，也是很考技术的。好好学学。
逛公园
学习了大佬题解。根据大佬的讲解，把对应部分分的代码打到一起了。（有点臃肿）
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=2e5+10;
#define re register
int tot,t,n,m,k,p,hd[N],vis[N],hdn[N],totn,id[N],idx[N];
int cnt[N],f[N][55],ans,deg[N],hd0[N],tot0,q[N];
ll dis[N],disn[N];
inline int read()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*f;
}
struct Edge{
int v,nx;ll w;
}e[M],en[M];
struct node{
int u;ll w;
node(){}
node(int _u,ll _w):u(_u),w(_w){}
bool operator <(const node&rhs)const{
return w>rhs.w;}
};
namespace pts30{
void add(int u,int v,ll w)
{
e[tot].v=v;
e[tot].nx=hd[u];
e[tot].w=w;
hd[u]=tot++;
}
void dijkstra()
{
memset(dis,0x7f,sizeof(dis));memset(vis,0,sizeof(vis));
priority_queue<node>q;dis[1]=0;q.push(node(1,0));cnt[1]=1;
while(q.size())
{
int u=q.top().u;q.pop();vis[u]=0;
for(int i=hd[u];~i;i=e[i].nx)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;cnt[v]=cnt[u];
if(!vis[v])vis[v]=1,q.push(node(v,dis[v]));
}
else if(dis[v]==dis[u]+e[i].w)
{
cnt[v]+=cnt[u];
if(cnt[v]>=p)cnt[v]-=p;
}
}
}
printf("%d\n",cnt[n]%p);
}
void solve()
{
using namespace pts30;
t=read();
while(t--)
{
memset(hd,-1,sizeof(hd));tot=0;
n=read();m=read();k=read();p=read();
int u,v;ll w;
for(int i=1;i<=m;i++)
u=read(),v=read(),w=read(),add(u,v,w);
dijkstra();
}
}
}
namespace pts70{
inline void add(int u,int v,ll w)
{
e[tot].v=v;
e[tot].nx=hd[u];
e[tot].w=w;
hd[u]=tot++;
}
bool cmp(const int &a,const int &b)
{
return dis[a]<dis[b];
}
void dijkstra()
{
memset(dis,0x7f,sizeof(dis));memset(vis,0,sizeof(vis));
priority_queue<node>q;dis[1]=0;q.push(node(1,0));
while(q.size())
{
int u=q.top().u;q.pop();vis[u]=0;
for(int i=hd[u];~i;i=e[i].nx)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])vis[v]=1,q.push(node(v,dis[v]));
}
}
}
}
void solve()
{
using namespace pts70;
t=read();
while(t--)
{
memset(hd,-1,sizeof(hd));tot=0;
memset(hdn,-1,sizeof(hdn));totn=0;
memset(f,0,sizeof(f));ans=0;
n=read();m=read();k=read();p=read();
int u,v;ll w;
for(int i=1;i<=m;i++)
u=read(),v=read(),w=read(),add(u,v,w);
dijkstra();
for(int i=1;i<=n;i++)id[i]=i;
sort(id+1,id+n+1,pts70::cmp);
f[1][0]=1;
for(int j=0;j<=k;j++)
for(int i=1;i<=n;i++)
{
int u=id[i];
for(int o=hd[u];~o;o=e[o].nx)
{
int v=e[o].v;ll w=e[o].w;
if(dis[u]+j+w-dis[v]<=k)
{
f[v][dis[u]+j+w-dis[v]]+=f[u][j];
if(f[v][dis[u]+j+w-dis[v]]>=p)f[v][dis[u]+j+w-dis[v]]-=p;
}
}
}
for(int j=0;j<=k;j++)
{
ans+=f[n][j];if(ans>=p)ans-=p;
}
printf("%d\n",ans);
}
}
}
namespace AC{
struct Edge0{
int v,nx;
}e0[M];
inline void add(int u,int v,ll w)
{
e[tot].v=v;
e[tot].nx=hd[u];
e[tot].w=w;
hd[u]=tot++;
}
inline void addn(int u,int v,ll w)
{
en[totn].v=v;
en[totn].nx=hdn[u];
en[totn].w=w;
hdn[u]=totn++;
}
inline void add0(int u,int v)
{
e0[tot0].v=v;
e0[tot0].nx=hd0[u];
hd0[u]=tot0++;
}
inline void dijkstran()
{
memset(disn,0x7f,sizeof(disn));memset(vis,0,sizeof(vis));
priority_queue<node>q;disn[1]=0;q.push(node(1,0));
while(q.size())
{
re int u=q.top().u;q.pop();vis[u]=0;
for(re int i=hdn[u];~i;i=en[i].nx)
{
re int v=en[i].v;
if(disn[v]>disn[u]+en[i].w)
{
disn[v]=disn[u]+en[i].w;
if(!vis[v])vis[v]=1,q.push(node(v,disn[v]));
}
}
}
}
inline void dijkstra()
{
memset(dis,0x7f,sizeof(dis));memset(vis,0,sizeof(vis));
priority_queue<node>q;dis[1]=0;q.push(node(1,0));
while(q.size())
{
re int u=q.top().u;q.pop();vis[u]=0;
for(re int i=hd[u];~i;i=e[i].nx)
{
re int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])vis[v]=1,q.push(node(v,dis[v]));
}
}
}
}
bool toposort()
{
re int h=1,t=0;
for(re int i=1;i<=n;i++)
if(!deg[i])q[++t]=i;
while(h<=t)
{
re int u=q[h++];
for(re int i=hd0[u];~i;i=e0[i].nx)
{
re int v=e0[i].v;
if(--deg[v]==0)q[++t]=v;
}
}
for(re int i=1;i<=n;i++)id[q[i]]=i;
for(re int i=1;i<=n;i++)
if(deg[i]&&dis[i]+disn[i]-dis[n]<=k)return true;
return false;
}
inline bool cmp(const int &a,const int &b)
{
return dis[a]<dis[b]||(dis[a]==dis[b]&&id[a]<id[b]);
}
inline void solve()
{
using namespace AC;
t=read();
while(t--)
{
memset(hd,-1,sizeof(hd));tot=0;
memset(hdn,-1,sizeof(hdn));totn=0;
memset(hd0,-1,sizeof(hd0));tot0=0;
memset(deg,0,sizeof(deg));memset(f,0,sizeof(f));ans=0;
n=read();m=read();k=read();p=read();
int u,v,w;
for(re int i=1;i<=m;i++)
{
u=read();v=read();w=read();add(u,v,w);addn(v,u,w);
if(!w)add0(u,v),deg[v]++;
}
dijkstra();dijkstran();
if(toposort()){puts("-1");continue;}
f[1][0]=1;
for(re int i=1;i<=n;i++)idx[i]=i;sort(idx+1,idx+n+1,cmp);
for(re int j=0;j<=k;j++)
for(re int i=1;i<=n;i++)
{
re int u=idx[i];
for(re int o=hd[u];~o;o=e[o].nx)
{
re int v=e[o].v;ll w=e[o].w;
if(dis[u]+w+j-dis[v]<=k)
{
f[v][dis[u]+w+j-dis[v]]+=f[u][j];
if(f[v][dis[u]+w+j-dis[v]]>=p)f[v][dis[u]+w+j-dis[v]]-=p;
}
}
}
for(re int i=0;i<=k;i++)
{
ans+=f[n][i];
if(ans>=p)ans-=p;
}
printf("%d\n",ans);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//pts30::solve();
//pts70::solve();
AC::solve();
return 0;
}
总结
首先看到路径数，想能不能DP转移，然后通过求出的最短路按照拓扑序进行转移，还得判断0环。
奶酪
打了一份并查集一份dfs的代码
#include<cstdio>
typedef long long ll;
const int N=1e3+10;
int set[N];
ll n,h,r;
struct node{
ll x,y,z;
}hole[N];//存点
void init()//初始化代表元全为自己
{
for(int i=0;i<=n+1;i++)
set[i]=i;
}
int findset(int x)//查找代表元
{
if(x==set[x])
return x;
else return set[x]=findset(set[x]);
}
void unionset(int x,int y)//并集
{
int fx=findset(x);
int fy=findset(y);
set[fy]=fx;
}
ll getdis(node a,node b)//返回两点间的距离的平方
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
int main()
{
//freopen("in.txt","r",stdin);
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&h,&r);//此处没写lld扣20
init();
int st=0,ed=n+1;//虚拟的起点终点
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&hole[i].x,&hole[i].y,&hole[i].z);//此处没写lld再扣10
if(hole[i].z<=r)unionset(i,st);//合并起点和i
if(hole[i].z>=h-r)unionset(i,ed);//合并终点和i
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(getdis(hole[i],hole[j])<=(4*r*r))unionset(i,j);//将相通的点合并
if(findset(st)==findset(ed))printf("Yes\n");//起点和终点在集合里说明连通
else printf("No\n");
}
return 0;
}
//链式前向星+dfs
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x7f7f7f7f;
using namespace std;
const int N1=2100000;//不开大点会RE
const int N2=1100;
typedef long long ll;
ll n,h,r,tot,flag;
//n空洞个数,h高度,r半径,tot存边用,flag标记是否有解
int head[N2],vis[N2];//head存边用,vis标记节点
struct node{
ll x,y,z;
}hole[N2];//长宽高
queue<int>q;//存起点
bool e[N2];//标记可行的终点
ll getdis(node a,node b)//返回距离的平方
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
struct Edge{
int to,nextx;
ll val;
}edge[N1];//链式前向星
void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].nextx=head[u];
head[u]=tot++;
}//添边
void dfs(int u)//搜索
{
if(e[u])//到达终点
{
flag=1;//标记为可行
return;
}
for(int i=head[u];i!=-1;i=edge[i].nextx)
{
int v=edge[i].to;//下个节点
if(!vis[v])//没走过
{
vis[v]=1;//标记
dfs(v);//遍历下个节点
if(flag)return;//已经可行不找了
//可以不用回溯了没啥用
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
int t,i,j;
scanf("%d",&t);//测试用例
while(t--)
{
while(!q.empty())q.pop();
flag=0;
tot=0;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(e,0,sizeof(e));//以上都是初始化
scanf("%lld%lld%lld",&n,&h,&r);
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&hole[i].x,&hole[i].y,&hole[i].z);
if(hole[i].z<=r)q.push(i);//可以作为起点
if(hole[i].z>=h-r)e[i]=1;//可以作为终点
}
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
if(getdis(hole[i],hole[j])<=4*r*r)//两点连通
{
addedge(i,j);
addedge(j,i);
}
while(!q.empty())
{
int st=q.front();
q.pop();
dfs(st);//从起点开始遍历
if(flag)break;
}
if(flag)
printf("Yes\n");
else printf("No\n");
}
return 0;
}
总结
好久以前写的
宝藏
学习了大佬题解，大概看明白了思路。
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,g[15][15],d[15][1<<13];
ll f[15][1<<13],ans=LONG_LONG_MAX;
//f[i][s]表示第i层状态为s时的最小代价
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);int S=1<<n;
int u,v,w;
memset(g,0x3f,sizeof(g));
for(int i=1;i<=m;i++)
scanf("%d%d%d",&u,&v,&w),g[u][v]=g[v][u]=min(g[u][v],w);
for(int i=1;i<=n;i++)
for(int s=1;s<S;s++)//找到s状态下i连出去的最小边
{
d[i][s]=INF;
for(int k=1;k<=n;k++)
if((1<<(k-1))&s)d[i][s]=min(d[i][s],g[i][k]);
}
for(int s1=1;s1<S;s1++)
{
if(s1&(s1-1))
for(int i=0;i<=n;i++)
f[i][s1]=INF;
for(int s2=s1&(s1-1);s2;s2=s1&(s2-1))//枚举子集
{
ll dis=0;//每一次的道路权值和
int s=s1^s2;
for(int k=1;k<=n;k++)
if((1<<(k-1))&s2)
dis+=d[k][s];
for(int k=1;k<=n;k++)
f[k][s1]=min(f[k][s1],f[k-1][s]+dis*k);
}
}
for(int i=1;i<=n;i++)
ans=min(ans,f[i][S-1]);
printf("%lld\n",ans);
return 0;
}
总结
复习一波状压DP，包括子集的枚举等等操作。
列队
专程找到大佬题解，去学一波线段树的动态开点（我这么蒟蒻怎么会动态开点呢QAQ）（当然更不会平衡树什么的QAQ）我会告诉你我快读里面ch^48没加括号RE4次吗qwq
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=6e5+10,M=2e7+10;
typedef long long ll;
int rt[N],sz,n,m,q,maxn,pos;
struct SegmentTree{
int sum,l,r;
SegmentTree(){l=r=0;}
}e[M];//以值为区间建树，区间和表示这段区间的数使用了多少次
vector<ll>g[N];
inline int read()
{
int f=0,s=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
inline void update(int &o,int l,int r)
{
if(!o)o=++sz;e[o].sum++;
if(l<r)
{
int mid=l+r>>1;
if(mid>=pos)update(e[o].l,l,mid);
else update(e[o].r,mid+1,r);
}
}
inline int query(int o,int l,int r,int x)
{
if(l==r)return l;
int mid=l+r>>1,szl=mid-l+1-e[e[o].l].sum;
if(szl>=x)return query(e[o].l,l,mid,x);
else return query(e[o].r,mid+1,r,x-szl);
}
inline ll solr(int x,ll v)//处理最后一列
{
pos=query(rt[n+1],1,maxn,x);update(rt[n+1],1,maxn);
ll ans=pos<=n?1ll*pos*m:g[n+1][pos-n-1];
g[n+1].push_back(v?v:ans);
return ans;
}
inline ll soll(int x,int y)//处理每一行
{
pos=query(rt[x],1,maxn,y);update(rt[x],1,maxn);
ll ans=pos<m?1ll*(x-1)*m+pos:g[x][pos-m];
g[x].push_back(solr(x,ans));
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
n=read();m=read();q=read();maxn=max(m,n)+q;
while(q--)
{
int x,y;x=read();y=read();
if(y==m)//最后一列
printf("%lld\n",solr(x,0));
else
printf("%lld\n",soll(x,y));
}
return 0;
}
总结
专程学习开n棵线段树再动态开点的操作。（改天学了splay再来写一遍）
赛后总结
其实就是去写（抄）了去年的题。感觉难度不小啊qwq，辣么多数据结构和DP都不会鸭qwq，希望最后一个月能咸鱼翻身鸭qwq