收到意见,认为每天的程序和随笔放在一起写的博客太长了,于是分开整理
day1
模拟赛,看了看提高a组t1的样例就不太想写,于是转而写b组
t1:
找出来k个标记点和起点到所有点的最短路,然后dfs经过k个点的顺序就可以啦!
当时主要犯了两个错误,1.没有判无解情况,2.设的初值为0x3f3f3f3f,有点小。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; struct NODE { int flg[11],cur; long long dis; }; struct Edge { int v,nxt,val; }e[100010]; int head[50010],n,m,k,s,t,cnt,flg,pa; long long dis[50010][11],vis[50010],num[50010]; int cut[50010]; long long ans; void add(int u,int v,long long val) { e[++cnt].nxt=head[u]; e[cnt].v=v; e[cnt].val=val; head[u]=cnt; } void spfa(int st,int now) { queue<int>q; for(int i=1;i<=n;i++) dis[i][now]=0xffffffff; for(int i=1;i<=n;i++) vis[i]=0; dis[st][now]=0; vis[st]=1; q.push(st); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(dis[v][now]>dis[u][now]+e[i].val) { dis[v][now]=dis[u][now]+e[i].val; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } void dfs(int lst_cur,int lst_num,long long ndis) { if(lst_num==k) { if(dis[t][lst_cur]==0xffffffff) return; ndis+=dis[t][lst_cur]; ans=min(ans,ndis); ndis-=dis[t][lst_cur]; flg=1; return ; } for(int i=1;i<=k;i++) { if(vis[i]) continue; if(dis[cut[i]][lst_cur]==0xffffffff) continue; vis[i]=1; ndis+=dis[cut[i]][lst_cur]; dfs(i,lst_num+1,ndis); ndis-=dis[cut[i]][lst_cur]; vis[i]=0; } return; } int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); for(int i=1;i<=m;i++) { int x,y; long long z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } if(k==0) { spfa(s,0); if(dis[t][0]==0xffffffff) dis[t][0]=-1; printf("%lld",dis[t][0]); } else { cut[0]=s; for(int i=1;i<=k;i++) { scanf("%d",&cut[i]); } for(int i=0;i<=k;i++) spfa(cut[i],i); for(int i=1;i<=k;i++) vis[i]=0; ans=0xffffffff; dfs(0,0,0); if(!flg) cout<<"-1"; else printf("%lld",ans); } return 0; }
t2:
Description
万老师听说某大国很流行穿越,于是他就想写一个关于穿越的剧本。
闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般,所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类:战役事件(CASE)、穿越回去事件(END)。战役事件可以选择是否参加,参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是,END事件如果满足要求就会强制发生。老师希望在大陆玩个够,所以他要求只有最后一个END事件会发生。老师希望获得最多的金钱,所以求助于你。
闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般,所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类:战役事件(CASE)、穿越回去事件(END)。战役事件可以选择是否参加,参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是,END事件如果满足要求就会强制发生。老师希望在大陆玩个够,所以他要求只有最后一个END事件会发生。老师希望获得最多的金钱,所以求助于你。
维护一个小根堆,每次遇见限制就弹出堆顶直到满足限制条件。这道题爆零爆的非常郁闷,特别注意一下最后一个条件只要rp大于要求就行,我理解错题意了,认为必须等于,于是用正确的方法却爆了零...
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; priority_queue<int>q; int main() { int n,cnt=0; int flg=0; char c; scanf("%d",&n); for(int i=1;i<n;i++) { cin>>c; if(c=='c') { int x; scanf("%d",&x); q.push(-x); cnt++; } if(c=='e') { int x; scanf("%d",&x); if(x==0) flg=1; x--; while(q.size()>x) { q.pop(); } } } cin>>c; int p; scanf("%d",&p); int ans=0; if(q.size()<p) flg=1; else { while(!q.empty()) { int t=q.top(); q.pop(); ans-=t; } } if(flg) ans=-1; cout<<ans; return 0; }
t3:
平面上有n个点,求出用这些点可以构成的三角形数。
当时很懵,强行打了个n^3暴力,用斜率判是否共线,给了50分(贼良心呀)。
正解是枚举一个点,求此点与其他点的斜率,斜率相同说明共线。记得不要重复计算。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long c[3010][5],ans; double lk[3010]; struct NODE { int x,y; }node[3010]; bool cmp(NODE a,NODE b) { if(a.y==b.y) return a.x<b.x; else return a.y<b.y; } int main() { freopen("triangle.in","r",stdin); freopen("triangle.out","w",stdout); int n; scanf("%d",&n); for(int i=0;i<=3010;i++) c[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; ans=c[n][3]; for(int i=1;i<=n;i++) scanf("%d%d",&node[i].x,&node[i].y); sort(node+1,node+1+n,cmp); int nn=n-1; for(int i=1;i<nn;i++) { int con=0,tot=0; for(int j=i+1;j<=n;j++) { if(node[j].x==node[i].x) { tot++; continue; } lk[++con]=(double)(node[j].y-node[i].y)/(double)(node[j].x-node[i].x); } sort(lk+1,lk+1+con); ans-=c[tot][2]; tot=1; for(int j=2;j<=con;j++) { if(lk[j]==lk[j-1]) tot++; else { if(tot==1) continue; ans-=c[tot][2]; tot=1; } } if(tot!=1) ans-=c[tot][2]; } cout<<ans; fclose(stdin); fclose(stdout); return 0; }
我这里还排了个序,其实应该不需要。
改完啦!