T122393 À la Volonté du Peuple
这题可以两种写法：
点有两个最短路前驱会爆，
边不在最短路上会爆。
第一种方法：暴力枚举每一个边和点，复杂度是O(n+m),而不是O（n*n)的，因为n和m同阶，达不到n^n的复杂度。
如果这样会爆，跑最短路就直接爆了，spfa肯定是O(n^n)的。总复杂度O（n+m)
#include<bits/stdc++.h> using namespace std; #define pb push_back const int inf=0x3f3f3f3f; const int maxn=3e5+5; struct edge{int v,w;edge(int a,int b){v=a,w=b;}};//v终点，w边权 struct node{ int id,dis;//id点编号 dis暂时距离 node(int a,int b){id=a,dis=b;} friend bool operator<(node a,node b){ return a.dis>b.dis;//每次让距离小出队 } }; vector<edge>e[maxn]; int dis[maxn];//记录最短路 bool done[maxn];//记录是否找到最短路 int n,m; void dijkstra(){ int s=1;//s起点 根据情况改 for(int i=0;i<=n;i++)dis[i]=inf,done[i]=0; dis[s]=0; priority_queue<node>Q; Q.push(node(s,0)); while(!Q.empty()){ node u=Q.top();Q.pop(); if(done[u.id])continue; done[u.id]=1; for(int i=0;i<e[u.id].size();i++){//遍历邻居 edge y=e[u.id][i]; if(done[y.v])continue; if(dis[y.v]>y.w+dis[u.id]){ dis[y.v]=y.w+u.dis; Q.push(node(y.v,dis[y.v]));//更新最短路 } } } } int main(){ cin>>n>>m; while(m--){ int a,b,c; scanf("%d %d %d",&a,&b,&c); e[a].pb(edge(b,c)); if(a!=b)e[b].pb(edge(a,c)); } dijkstra(); int ans=0,cnt; for(int i=1;i<=n;i++){ cnt=0; for(int j=0;j<e[i].size();j++){ int y=e[i][j].v; if(dis[i]==dis[y]+e[i][j].w)cnt++; if(i>=y&&dis[i]<dis[y]+e[i][j].w&&dis[y]<dis[i]+e[i][j].w)ans++; } if(cnt>1)ans++; } cout<<ans<<endl; return 0; }
第二种方法：
比较鬼。
最短路前驱为1，不炸。
最短路前驱>=2,会少炸x-1次
考虑这样理解：
如果开始所有点used都为0，那么m条边都会炸，即ans=m；
对边而言
一个边如果炸了（不在最短路上），对边的两端used必然贡献为0，因为两边都不能更新最短路，都不会有最短路前驱
如果一个边不炸（在最短路上），那么必然会对一个点的used+1，也就是说不炸的边等价于used总和
即ans-=used[i];
对点而言
如果used>=2会炸，ans++;
总结一下：
ans=m
for i ans-=used
for i used>=2 ans++
#include<bits/stdc++.h> using namespace std; #define pb push_back const int inf=0x3f3f3f3f; const int maxn=3e5+5; struct edge{int v,w;edge(int a,int b){v=a,w=b;}};//v终点，w边权 struct node{ int id,dis;//id点编号 dis暂时距离 node(int a,int b){id=a,dis=b;} friend bool operator<(node a,node b){ return a.dis>b.dis;//每次让距离小出队 } }; vector<edge>e[maxn]; int dis[maxn];//记录最短路 bool done[maxn];//记录是否找到最短路 int n,m; int used[maxn]; void dijkstra(){ int s=1;//s起点 根据情况改 for(int i=0;i<=n;i++)dis[i]=inf,done[i]=0; dis[s]=0; priority_queue<node>Q; Q.push(node(s,0)); while(!Q.empty()){ node u=Q.top();Q.pop(); if(done[u.id])continue; done[u.id]=1; for(int i=0;i<e[u.id].size();i++){//遍历邻居 edge y=e[u.id][i]; if(done[y.v])continue; if(dis[y.v]>y.w+dis[u.id]){ dis[y.v]=y.w+u.dis; used[y.v]=1; Q.push(node(y.v,dis[y.v]));//更新最短路 } else if(dis[y.v]==y.w+dis[u.id])used[y.v]++; } } } int main(){ memset(used,0,sizeof used); cin>>n>>m; int ans=m; while(m--){ int a,b,c; scanf("%d %d %d",&a,&b,&c); e[a].pb(edge(b,c)); if(a!=b)e[b].pb(edge(a,c)); } dijkstra(); for(int i=1;i<=n;i++){if(used[i]>=2)used[i]--;ans-=used[i];} cout<<ans<<endl; // system("pause"); return 0; }
T122394 Billionaire
zeller公式二分出日期答案，或者暴力按月 跳优化。
#include<bits/stdc++.h> using namespace std; int getId(int y, int m, int d) { if (m < 3) {y --; m += 12;} return 365 * y + y / 4 - y / 100 + y / 400 + (153 * (m - 3) + 2) / 5 + d - 307; } vector<int> date(int id) { int x = id + 1789995, n, i, j, y, m, d; n = 4 * x / 146097; x -= (146097 * n + 3) / 4; i = (4000 * (x + 1)) / 1461001; x -= 1461 * i / 4 - 31; j = 80 * x / 2447; d = x - 2447 * j / 80; x = j / 11; m = j + 2 - 12 * x; y = 100 * (n - 49) + i + x; vector<int>v; v.push_back(y),v.push_back(m),v.push_back(d); return v; } int m; const int maxn=1000000000; bool check(int x){ int sum=m+x*(x+1)/2; if(sum>=maxn)return 1; else return 0; } int main(){ int t; cin>>t; while(t--){ int ty,tm,td; scanf("%d %d %d %d",&m,&ty,&tm,&td); int id=getId(ty,tm,td); int l=0,r=sqrt(2e9); while(l<=r){ int mid=(r+l)/2; if(check(mid))r=mid-1; else l=mid+1; } id+=l; vector<int>ans=date(id); printf("%d %d %d ",ans[0],ans[1],ans[2]); } // system("pause"); return 0; }