比赛开始看了看T1 very Good 有思路，直接用手动全排列A掉（虽然卡了5min左右但get100pt），转过来看T2用暴力模拟A掉（get100pt），接着看T3 虽然第一眼因为最大值最小看成了二分，但很快否决了，这指定是一道多源最短路，但是当时脑子亿抽写了一个适用于单源最短路的bellmaxnford还出了一些错误最后拿了（55pt），T3正解为弗洛伊德。至于T4，想出了各位2 4 8 6的变化周期，但没有思路写程序就写了一个能拿30pt的DFS保分（get30pt） 最后得分285pt
TIPS： 1. floyd 初始化：memset(dis, 0x3F, sizeof(dis))，然后要记得把 dis[i][i] 设为 0 2. 利用 reverse 翻转 string 3. 全源最短路最好还是采用 floyd，另外使用 BellmanFord 时注意双向边问题 4. n的规模和时间复杂度一般是对应的： n | 10 20+ 40 100 500 5000 10^5 10^6 10^7 O | n! 2^n n^5/2^(n/2) n^4 n^3 n^2 nlog^2(n)/n*sqrt(n) nlogn n
T3题解：
题意：给定一张 n 个点 m 条边的无向图，边有正边权。求一个点使得其到其 他点的最短路的最大值最小。 看到 n ≤ 500，直接 floyd 求出任意两点间的最短路后统计答案即可。 T4题解： 一道数字讨论题。 观察在进行操作后数字的个位会产生什么变化。 5 会变为 0， 0 不动；而 1, 3, 7, 9 变一次后会分别变为 2, 6, 4, 8；对于 2, 6, 4, 8 来说，会按照 2 → 4 → 8 → 6 → 2 的顺序不断循环。 所以，个位为 5 的数字操作一次之后就无法再动，为 0 的无论如何操作都不 会动；而对于 1, 3, 7, 9 而言，操作一次后会变为偶数，对于 2, 6, 4, 8 而言，操作 四次后每 4 轮操作会循环地加上 20。 所以，如果同时出现了个位为 5, 0 以及其他的数字，那么自动无解；如果只 出现了 5, 0，将所有数字一起操作一次之后判断即可（对于 0 来说没有影响）； 如果没有出现 5, 0，则考虑将所有数字的个位操作到 2，然后固定个位，每 4 次操作加上二十，所以只需要看除了个位之外的数字是不是同时是奇数和偶数即 可。 T1程序：#include<bits/stdc++.h>
using namespace std;
int p(int a,int b,int c)
{
int ans=0;
if(a%10==0) ans+=a;
else ans+=a+10-a%10;
if(b%10==0) ans+=b;
else ans+=b+10-b%10;
ans+=c;
return ans;
}
int main()
{
freopen( "ord.in", "r", stdin );
freopen( "ord.out", "w", stdout );
ios::sync_with_stdio(false);
int a,b,c;
cin>>a>>b>>c;
cout<<min(p(a,b,c),min(p(a,c,b),min(p(b,a,c),min(p(b,c,a),min(p(c,a,b),p(c,b,a))))));
// cout<<p(b,c,a);
return 0;
}
T2程序：
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen( "cip.in", "r", stdin );
freopen( "cip.out", "w", stdout );
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
string s,s1;
cin>>s;
// cout<<s;
for(int i=s.length()-1,j=0;i>=0;i--,j++)
{
if(s[i]=='b') s1+='d';
if(s[i]=='d') s1+='b';
if(s[i]=='p') s1+='q';
if(s[i]=='q') s1+='p';
}
// cout<<s1<<endl;
if(s1==s) printf("yes\n");
else printf("no\n");
}
return 0;
}
T3程序：
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int ans[N];
int dis[N][N];
int main()
{
ios::sync_with_stdio(false);
memset(dis,0x3F,sizeof(dis));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
}
for (int i=1;i<=n;i++) dis[i][i] = 0;
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
int mini=1e9;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) ans[i]=max(ans[i],dis[i][j]);
mini=min(mini,ans[i]);
}
cout<<mini<<endl;
for(int i=1;i<=n;i++) if(ans[i]==mini) cout<<i<<" ";
return 0;
}
T4程序：
#include <iostream>
using namespace std;
const int maxN = 1e5 + 5;
int n;
int a[maxN], cnt[maxN];
int buk[10];
int Oper(int x)
{ return x + (x % 10); }
int main()
{
#ifndef ONLINE_JUDGE
freopen("num.in", "r", stdin);
freopen("num.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i], ++buk[a[i] % 10];
if (buk[5] != 0 or buk[0] != 0)
{
for (int i = 1; i <= n; ++i)
{
if (a[i] % 10 != 0 and a[i] % 10 != 5)
{
cout << "-1" << endl;
return 0;
}
if (a[i] % 10 == 5)
cnt[i] = 1, a[i] = Oper(a[i]);
if (i != 1 and a[i] != a[i - 1])
{
cout << "-1" << endl;
return 0;
}
}
for (int i = 1; i <= n; ++i)
cout << cnt[i] << ' ';
cout << endl;
return 0;
}
for (int i = 1; i <= n; ++i)
while (a[i] % 10 != 2)
++cnt[i], a[i] = Oper(a[i]);
int maxi = 0;
buk[0] = buk[1] = 0;
for (int i = 1; i <= n; ++i)
{
++buk[(a[i] / 10) % 2];
maxi = max(maxi, a[i]);
}
if (buk[0] and buk[1])
cout << -1 << endl;
else
{
for (int i = 1; i <= n; ++i)
cnt[i] += (maxi - a[i]) / 20 * 4;
for (int i = 1; i <= n; ++i)
cout << cnt[i] << ' ';
cout << endl;
}
return 0;
}
标签：10,int,cin,集训,freopen,ans,Day,dis From： https://www.cnblogs.com/wjk53233/p/17591554.html