http://acm.hdu.edu.cn/diy/contest_show.php?cid=36390
能猜对多少呢？
Time Limit : 3000/1000ms (Java/Other)
Memory Limit : 65535/32768K (Java/Other)
Problem Description
由于疫情的原因，大家最近都在家学习，但是这样有个问题，作业只能在网上提交。
而这样的问题导致大家都不想拿草稿纸计算，也不想动脑子，就想着随机猜答案！
老师布置了 n 道单项选择题，每道题目分别有 a[i] 个选项，而对于每道题，你都会随机猜一个答案，等所有选项都填好以后就急迫地点击提交。
但是系统竟然在这个时候出BUG了！每个题的填写的答案都跑到下一个题那里去了（最后一个题到了第一个题那里）。那么请问这时你做对的题目数期望是多少呢？
Input
输入包含 T 组数据，即第一行输入一个正整数 T (T ≤ 100)。
每组数据包含两行：
第一行一个正整数 n (n ≤ 10000)；
第二行 n 个正整数，分别表示 a[i] (a[i] ≤ 1e4)。
Output
输出包含 T 行，每行一个保留两位小数的数字，表示每组数据的答案。
Sample Input
1
3
3 3 3
Sample Output
1.00
solution
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main() {
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int a[n+1];
for(int i=0;i<n;++i) scanf("%d",&a[i]);
double ans=0;
for(int i=1;i<n;++i) ans+=1.0/max(a[i],a[i-1]);
ans+=1.0/max(a[n-1],a[0]);
printf("%.2f\n",ans);
}
return 0;
} 分两种情况讨论：
第一种情况是 第一题有5个选项 第二题3个选项
第二种情况是 第一题有3个选项 第二题5个选项
前者做对第二题概率是1/5
后者也是
来做做回文串吧
Problem Description
这题就直入主题吧。
给定一个长度为 n 的字符串，你需要选择它的一个前缀，在后面接上加上它的一个后缀，可以得到一个“前后缀串”（选择的前缀后都可以为空串，但总长度不超过原串）。如果这个串回文串那就更好了，所以问题就是，最长的回文前后缀串长度是多少呢？
Input
输入包含 T (T ≤ 30) 组数据。
接下来有 T 行，每行一个字符串，字符串长度不超过 1000。
Output
输出包含 T 行，每行一个正整数表示最长的回文前后缀串的长度。
Sample Input
1
abcefedcba
Sample Output
9
（Hint: 最长的为 abcefecba，前缀取abcefe，后缀取cba）
solution
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
#include <string>
using namespace std;
string s;
int pos;
inline int findleft(){
int L=pos,R=s.length()-pos-1;
char ch=s[L];
for(;L<R;R--){
if(ch==s[R]){
int l=L+1,r=R-1;
while(l<r&&s[l]==s[r])l++,r--;
if(l>=r) return R-L+1;
}
}
return 1;
}
inline int findright(){
int L=pos,R=s.length()-pos-1;
char ch=s[R];
for(;L<R;++L){
if(ch==s[L]){
int l=L+1,r=R-1;
while(l<r&&s[l]==s[r])l++,r--;
if(l>=r) return R-L+1;
}
}
return 1;
}
int solve() {
int L=0,R=s.length()-1;
for(; s[L]==s[R]&&L<R; L++,R--);
pos=L;
int ans=L*2;
//printf("pos=%d\n",pos);
--L,++R;
if(R-L>1)ans+=max(findleft(),findright());
return ans;
}
int main() {
int T,n;
scanf("%d",&T);
while(T--) {
cin>>s;
printf("%d\n",solve());
}
return 0;
} 两端匹配回文串，再搜索左中段回文串和右中段回文串，比出max相加即得结果。
最小生成树
Problem Description
由于种种奇怪的原因，这道题目被换成了考察最小生成树了。
有 n 个节点，然后给定 n * n 的矩阵，其中 a[i][j] 这个元素表示节点 i 到节点 j 之间边的边权。然后求最小生成树。本题请不要在网上查阅资料，自行完成。
Input
输入还是包含 T (T ≤ 4) 组数据。
每组数据先给定一个正整数 n (n ≤ 500)；
然后再给出一个 n * n 的矩阵，矩阵中的元素大小不超过 1e4。
（矩阵元素满足 a[i][i] = 0, a[i][j]=a[j][i]）
Output
输出也要包含 T 行，每行一个正整数，表示每组数据的答案啦。
Sample Input
1
3
0 1 1
1 0 1
1 1 0
Sample Output
2
solution
//kruskal
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 500*500 + 7;
int bin[maxn];
int n,m;
struct edge {
int u, v, w;
}
edges[maxn];
inline void unit() {
for (int i = 0; i <= m; i++) bin[i] = i;
}
inline int Find(int x) {
int px = x;
while (px != bin[px]) px = bin[px];
return px;
}
inline void merge(int x, int y) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) bin[fx] = fy;
}
inline bool cmp(edge a, edge b) { //定义排序规则
return a.w < b.w;
}
inline void Kruskal() {
long long int sumweight = 0; //生成树的权值
int num = 0; //已选用的边的数目
int u, v; //选用边的两个顶点
unit(); //初始化 parent[]数组
for (int i = 0; i < m; i++) {
u = edges[i].u;
v = edges[i].v;
if (Find(u) != Find(v)) { //判断其是否在同一个连通分量
//printf("%d %d %d\n", u, v, edges[i].w);
sumweight += edges[i].w;
num++;
merge(u, v);
}
if (num >= n - 1) break;
}
printf("%lld\n", sumweight);
}
int main() {
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);//读入顶点个数 n
int x;
m=0;
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
scanf("%d",&x);
if(x) {
edges[m].u = i+1;
edges[m].v = j+1;
edges[m++].w = x;
}
}}
sort(edges, edges + m, cmp);//排序
Kruskal();
}
return 0;
} //prim
#include "bits/stdc++.h"
using namespace std;
const int maxn = 5e2+7;
int n;
int dis[maxn], vis[maxn], e[maxn][maxn];
int Prim() {
int ans=0;
for(int i=0; i<=n; ++i) dis[i]=2e9, vis[i]=0; //初始化
dis[1]=0; //prim算法任选起点，于是可以选择1为起点
for(int i=1; i<=n; ++i) {
int u=0; //注意dis[0]已经初始化为无穷大了，不用管了
for(int j=1; j<=n; ++j) if(!vis[j]) {
if(dis[j]<dis[u]) u=j;
}
vis[u]=1; ans+=dis[u]; //更新答案啦
for(int j=1; j<=n; ++j) if(!vis[j]) { //拿u点来更新新拓展的边
if(dis[j]>e[u][j]) dis[j]=e[u][j];
}
}
return ans;
}
void solve() {
scanf("%d", &n);
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j) scanf("%d", &e[i][j]);
printf("%d\n", Prim());
}
int main() {
int T; cin>>T;
while(T--) solve();
} 
京公网安备 11010502036488号