华北水利水电大学第一届acm程序设计大赛
成功申请为校级比赛，所以称第一届，实为第三届。
题目描述
silechen有一颗骰子，他喜欢跟骰子玩游戏，一开始他将骰子平放在地上，然后骰子按照silechen的指令在地上滚动，silechen想将知道骰子每次接触地面的面(也就是骰子的下面)的值加起来是多少(注意，一开始接触地面的值也要算进去)？
输入
第一行是数据组数 1<=T<=10 接下来每组数据
第二行是6个整数，表示骰子的前、后、左、右、上、下的值是多少
第三行1<=n<=100000
第四行是n个整数,表示silenchen每次发出的指令
指令有4种
0:表示骰子向前滚动一次
1:表示骰子向后滚动一次
2:表示骰子向左滚动一次
3:表示骰子向右滚动一次
输出
输出T行，每行一个整数ans,表示每次骰子接触地面的面加起来的值(保证ans在int范围内)。
样例输入
1
1 2 3 4 5 6
4
0 1 2 3样例输出
22提示
一开始接触地面的值为骰子朝下的值
题目描述
silechen做助教，帮老师登记成绩，他看到[50,59]分的人于心不忍，想抢救一下他们（给他们登记成60分），silechen想知道他需要抢救多少人
输入
第一行是数据组数 1<=T<=10 接下来每组数据 第一行是 1<=n<=100000 接下来n个整数 0<=ai<=100 表示学生的成绩
输出
输出T行，每行一个整数ans,表示silechen需要抢救多少人。
样例输入
1
5
49 50 51 60 61样例输出
2提示
抢救分数为59、51的两个人
题目描述
输入
There are multiple test cases. The firstline of input contains an integer T(1<=T<=50), indicating the number of test cases. Foreach test case:
The first line contains one integern (0<n<50), indicating the number of all points. Then the next nlines, each lines contains three numbers xi,yi,zi (0<=xi,yi,zi<100000)indicating the position ofi-th point.
输出
For each test case, output a line, whichshould accurately rounded to two decimals.
样例输入
2
2
1 1 0
2 2 0
3
1 2 3
0 0 0
1 1 1样例输出
1.41
3.97代码如下：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int pre[55];
struct node
{
double x,y,z;
} p[55];
struct edge
{
int u,v;
double cost;
} e[2505];
int fin(int x)
{
if(x==pre[x])
{
return x;
}
else
{
return pre[x]=fin(pre[x]);
}
}
void join(int x,int y)
{
int t1=fin(x);
int t2=fin(y);
if(t1!=t2)
{
pre[t1]=t2;
}
}
double dist(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
bool cmp(edge a,edge b)
{
return a.cost<b.cost;
}
int main()
{
int n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
}
if(n==1)
{
printf("0.00\n");
continue;
}
for(int i=0;i<n;i++)
{
pre[i]=i;
}
int s=0;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
e[s].u=i;
e[s].v=j;
e[s++].cost=dist(p[i],p[j]);
}
}
sort(e,e+s,cmp);
double sum=0;
int ss=0;
for(int i=0;i<s;i++)
{
if(fin(e[i].u)!=fin(e[i].v))
{
join(e[i].u,e[i].v);
sum+=e[i].cost;
ss++;
}
if(ss==n-1)
{
break;
}
}
printf("%.2lf\n",sum);
}
return 0;
}题目描述
silchen有n个数字ai, dark di看到了之后打算给silchen出一个难题。他提出了M个问题，对于每个问题他都提出了一个数字x,要求silchen告诉他下标[x,n]之间有几个不同的数字。
输入
第一行输入一个数字T,表示数据组数,t小于等于5 每组数据的第1行输入2个整数，分别表示n,m, n,m均不大于100000. 第2行输入n个整数ai，保证ai不大于100000. 接下去m行每行1个整数，表示x, x的范围在1到n之间。
输出
对于每组数据，输出m行，每行一个数字，表示不同的数字个数。
样例输入
1
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10
样例输出
6
6
6
6
6
5
4
3
2
1#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[123456];
bool vis[123456];
int s[123456];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
s[n]=1;
vis[a[n]]=1;
for(int i=n-1;i>=1;i--)
{
if(!vis[a[i]])
{
vis[a[i]]=1;
s[i]=s[i+1]+1;
}
else s[i]=s[i+1];
}
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
cout<<s[x]<<endl;
}
return 0;
}题目描述
郑州市一共有n个公交站，Yellowstar家住在1号公交站，学校在n号公交站。作为一个走读的学生，Yellowstar每天都要早起坐公交车到学校。Yellowstar并不关心到学校所花费的时间，他只知道每次换乘公交车需要花费一块钱(相当于连续乘坐同一班次的公交不需要花钱)，由于交通管制他可能需要在换乘上多花费掉不少钱。 作为一个土生土长的郑州人，Yellowstar知道所有线路的信息，信息包括每条线路的起点站和终点站以及属于哪班次公交车。请你帮他计算，他从家里坐公交车到学校所需要的最小花费。
输入
第一行是样例数 1 <= T <= 20。 每组样例第一行给定n，m，表示一共有n个站点，m条线路 (1 <= n, m <= 100000)。 接下来m行为线路信息，每条线路包含u, v, x，表示起点站为u，终点站为v，公交车班次为x(1 <= u, v <= n, 1 <= x <= 100000)。
输出
输出T行，每行输出最小花费，如果公交线路无法到达学校，输出-1。
样例输入
1
3 3
1 2 2
2 3 2
1 3 1
样例输出
1提示
选择路线1->2, 2->3，都是2号班次的公交车，换乘不用花钱
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5e5 + 7;
//--------head---------
struct Edge {
int u, v, c;
void in() {
scanf("%d%d%d", &u, &v, &c);
}
} E[N];
int n, m, tot;
map<pii, int> R;
map<pii, int>::iterator it;
vector<pii> e[N];
void ins(int u, int c) {
pii p = mp(u, c);
if (R.find(p) == R.end())
R[p] = ++tot;
}
void addEdge(int u, int v, int c) {
int x = R[mp(u, c)], y = R[mp(v, c)];
e[x].pb(mp(v, 0)), e[x].pb(mp(y, 0));
}
bool vis[N];
int dis[N];
priority_queue<pii> que;
int solve() {
rep(i, 0, tot + 1)
vis[i] = false, dis[i] = -1;
que.push(mp(0, 1));
while (!que.empty()) {
int u = que.top().second, d = -que.top().first;
que.pop();
if (vis[u])
continue;
dis[u] = d, vis[u] = true;
rep(i, 0, sz(e[u])) {
int v = e[u][i].first, w = e[u][i].second;
if (!vis[v])
que.push(mp(-(d + w), v));
}
}
int ans = dis[n];
rep(i, 0, sz(e[n])) {
int v = e[n][i].first;
if (~dis[v] && (ans == -1 || dis[v] < ans))
ans = dis[v];
}
return ans;
}
int main() {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
tot = n;
R.clear();
rep(i, 0, m) {
E[i].in();
ins(E[i].u, E[i].c), ins(E[i].v, E[i].c);
}
for (int i = 1; i <= tot; i++) e[i].clear();
for (it = R.begin(); it != R.end(); ++it) {
pii p = it->first;
int v = it->second;
e[p.first].pb(mp(v, 1));
}
rep(i, 0, m) {
int u, v, c;
u = E[i].u, v = E[i].v, c = E[i].c;
addEdge(u, v, c), addEdge(v, u, c);
}
printf("%d\n", solve());
}
return 0;
}
题目描述
程序设计对抗赛有N（0<N<=50的整数）个价值互不相同的奖品，每个奖品的价值分别为S1，S2，S3......Sn(均为不超过100的正整数）。现将它们分给甲乙两队，为了使得甲乙两队得到相同价值的奖品，必须将这N个奖品分成总价值相等的两组。
编程要求：对给定N及N个奖品的价值，求出将这N个奖品分成价值相等级的两组，共有多少种分法？
例如：N=5，S1，S2，S3......Sn分别为1，5，3，8，9。则可分为{1，3，9}与{5，8}，仅有1种分法。
例如：N=7，S1，S2，S3.......Sn分别为1，2，3，4，5，6，7。
有4种分法：
{1，6，7}与{2，3，4，5}；
{2，5，7}与{1，3，4，6}；
{3，4，7}与{1，2，5，6}；
{1，2，4，7}与{3，5，6}；
输入
输入包含N及S1，S2，S3......Sn。（每两个相邻的数据之间有一个空格隔开）。
输出
输出包含一个整数，表示多少种分法的答案，数据若无解，则输出0。
样例输入
7
1 2 3 4 5 6 7样例输出
4#include<bits/stdc++.h>
using namespace std;
int a[51];
int dp[51][5010];
int main()
{
int n,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%2!=0)
{
printf("0");
return 0;
}
sum/=2;
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
dp[i][j]=dp[i-1][j];
if(j-a[i]>=0)
dp[i][j]=dp[i][j]+dp[i-1][j-a[i]];
}
}
printf("%d\n",dp[n][sum]/2);
return 0;
} 题目描述
To facilitate the analysis of a DNA sequence, a DNA sequence is represented by a binary number. The group of DNA-1 has discovered a great new way . There is a certain correlation between binary number and prime number. Instead of using the ordinary decadic numbers, they use prime base numbers. Numbers in this base are expressed as sequences of zeros and ones similarly to the binary numbers, but the weights of bits in the representation are not powers of two, but the elements of the primes ( 2, 3, 5, 7,... ). For example 01101 , ie. 2+5+7=14 Herefore, it is necessary to convert the binary number to the sum of prime numbers
输入
The input consists of several instances, each of them consisting of a single line. Each line of the input contains a 01 string, length of not more than 150. The end of input is not marked in any special way.
输出
For each test case generate a single line containing a single integer , The sum of the primes.
样例输入
000010
0011
11001样例输出
3
5
20赛后感：被学长们吊着打啊，真的是一点活路都不留。罚时很重要，难受。但比赛举办还是很顺利的，愿我华水acm越办越好，队员越来越强。