2018.10.10考试总结
T110078. 「一本通 3.2 练习 4」新年好
题目描述
原题来自:CQOI 2005
重庆城里有 个车站, 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接,从任何一个车站出发都可以经过一条或者多条公路到达其他车站,但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 ,他有五个亲戚,分别住在车站 ,,,,。过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福。怎样走,才需要最少的时间?
输入格式
第一行:, 为车站数目和公路的数目。
第二行:,,,, 为五个亲戚所在车站编号。
以下 行,每行三个整数 ,,,为公路连接的两个车站编号和时间。
输出格式
输出仅一行,包含一个整数 ,为最少的总时间。
样例
样例输入
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
####样例输出
21
###数据范围与提示
对于全部数据,,,,,
正解是求点1和五个亲戚的点到所有点的最短路,然后dfs求怎样排序最优
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define inf 0x7ffffff using namespace std; const int N=50005; struct node { int to,nxt,w; }e[N<<2]; int head[N],tot=0,a[10]; int dt[50]; int dis[7][N],vis[N],vis2[N]; int n,m,ans=inf; void add(int x,int y,int z) { e[++tot]=(node){y,head[x],z}; head[x]=tot; } void spfa(int s,int k) { queue<int>q; memset(vis2,0,sizeof(vis2)); q.push(s); vis2[s]=1; dis[k][s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis2[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(dis[k][v]>dis[k][u]+e[i].w) { dis[k][v]=dis[k][u]+e[i].w; if(!vis2[v]) { vis2[v]=1; q.push(v); } } } } } void dfs(int k) { if(k==6) { int s=0; for(int i=1;i<6;i++) s+=dis[dt[i]][a[dt[i+1]]]; ans=min(ans,s); return; } for(int i=2;i<=6;i++) { if(!vis[i]) { vis[i]=1; dt[k+1]=i; dfs(k+1); vis[i]=0; } } } int main() { scanf("%d%d",&n,&m); for(int i=2;i<=6;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } memset(dis,0x3f,sizeof(dis)); a[1]=1; dt[1]=1; for(int i=1;i<=6;i++) spfa(a[i],i); dfs(1); printf("%d",ans); return 0; }
T210178. 「一本通 5.5 例 4」旅行问题
题目描述
原题来自:POI 2004
John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 n 车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),行驶过程中不能出现没有油的情况。
任务:判断以每个车站为起点能否按条件成功周游一周。
输入格式
第一行是一个整数 ,表示环形公路上的车站数;
接下来 行,每行两个整数 ,,分别表示表示第 号车站的存油量和第 号车站到下一站的距离。
输出格式
输出共 行,如果从第 号车站出发,一直按顺时针(或逆时针)方向行驶,能够成功周游一圈,则在第 行输出 TAK,否则输出 NIE。
样例
样例输入
5
3 1
1 2
5 2
0 1
5 4
####样例输出
TAK
NIE
TAK
NIE
TAK
###数据范围与提示
对于全部数据 ,,.
正解单调队列
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N=2e6+1; int n,a[N],head,tail,pq[N],last; long long q[N],p[N],qz[N]; bool ans[N]; void work1() { for(int i=1;i<=2*n-1;i++) qz[i]=qz[i-1]+a[i]; head=1;tail=0; for(int i=1;i<=2*n-1;i++) { while(head<=tail&&q[tail]>=qz[i]) tail--; q[++tail]=qz[i]; p[tail]=i; while(head<=tail&&i-p[head]>=n) head++; if(i>=n) { if(q[head]>=qz[i-n]) ans[i-n+1]=1; } } return ; } void work2() { qz[1]=pq[1]; for(int i=2;i<=n+1;i++) qz[i]=qz[i-1]+pq[n-i+2]; for(int i=n+2;i<=n*2-1;i++) qz[i]=qz[i-1]+pq[n*2-i+2]; head=1;tail=0; for(int i=1;i<=2*n-1;i++) { while(head<=tail&&q[tail]>=qz[i]) tail--; q[++tail]=qz[i]; p[tail]=i; while(head<=tail&&i-p[head]>=n) head++; if(i>=n) { if(q[head]>=qz[i-n]) { if(i==n) ans[1]=1; else ans[2*n-i+1]=1; } } } return ; } int main() { scanf("%d",&n); for(int i=1,u,v;i<=n;i++) { scanf("%d%d",&u,&v); a[i+n]=a[i]=u-v; pq[i+n]=pq[i]=u-last; last=v; } pq[1]-=last; pq[1+n]=pq[1]; work1(); work2(); for(int i=1;i<=n;i++) { if(ans[i])puts("TAK"); else puts("NIE"); } return 0; }
T310220. 「一本通 6.5 例 2」Fibonacci 第 n 项
题目描述
大家都知道 Fibonacci 数列吧,,,,,⋯ ,。
现在问题很简单,输入 和 ,求 。
输入格式
输入 ,。
输出格式
输出 。
样例
样例输入
5 1000
####样例输出
5
###数据范围与提示
对于 100%100%100% 的数据, ,
矩阵快速幂板子
#include<iostream> #include<cstdio> #include<cstring> #define int long long using namespace std; int mod; struct node { int a[2][2]; }ss,ans; node mul(node &a,node &b) { node c; for(int i=0;i<2;++i) for(int j=0;j<2;++j) { c.a[i][j]=0; for(int k=0;k<2;++k) c.a[i][j]=(c.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod; } return c; } void fpow(int b) { while(b) { if(b&1)ans=mul(ans,ss); ss=mul(ss,ss); b>>=1; } } signed main() { int n; scanf("%lld%lld",&n,&mod); ans.a[0][0]=ans.a[1][0]=1; ans.a[0][1]=ans.a[1][1]=0; ss.a[0][0]=ss.a[1][0]=ss.a[0][1]=1; ss.a[1][1]=0; fpow(n-1); printf("%lld",ans.a[0][0]); return 0; }