BNUZ-ACM 2018国庆新生欢乐赛题解
目录
A.三角恋
给你n个数，编号为1到n,每个数的值为非自己本身的另外一个数的编号，求是否存在三元环。
n最大为5000，直接暴力循环枚举最多5000次就够，简单思维题。
#include<stdio.h>
int main() {
int T, n;
int a[5005];
scanf("%d", &T);
int cas = 1;
while(T--) {
scanf("%d", &n);
int flag = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i++) {
if(a[a[a[i]]] == i){
flag = 1;
break;
}
}
if(flag){
printf("Case #%d: 苦海无涯\n",cas++);
}else {
printf("Case #%d: 嘤嘤嘤\n",cas++);
}
}
return 0;
}
B.台风闲聊
题目里面给了细节每个人只能取一次，所以只要场上存在的编号超过两种，肯定不公平，
只有一种，那么其中一个人肯定没有牌，也不公平，
存在两种，判断是否数量相同就可以
#include<stdio.h>
#include<string.h>
int num[1000];
int main() {
int n, T, cas = 1;
scanf("%d",&T);
while(T--) {
scanf("%d", &n);
memset(num,0,sizeof(num));
int a, b = 0, c = 0, flag = 1;
for(int i = 0; i < n; i++) {
int a;
scanf("%d",&a);
num[a]++;
}
for(int i = 1; i <= 100 ; i++) {
if(num[i] != 0) {
if(b == 0) {
b = i;
} else if(c == 0) {
c = i;
} else {
flag = 0;
}
}
}
if(num[b] != num[c]) {
flag = 0;
}
printf("Case #%d: ",cas++);
if(flag) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
} C.kuyee买奶茶
输入的数字位数超过100位，所以不能用int 或者long long int 输入
使用字符串输入即可
对每一位字符进行判断即可
#include<stdio.h>
#include<string.h>
int main() {
int T, cas = 1;
char ss[105];
scanf("%d",&T);
while(T--) {
scanf("%s",ss);
int count = 0;
for(int i = 0; i < strlen(ss); i++) {
if(ss[i] == '0' || ss[i] == '4' || ss[i] == '6' || ss[i] == '9') {
count++;
} else if(ss[i] == '8') {
count += 2;
}
}
printf("Case #%d: %d\n", cas++, count);
}
return 0;
} D.法师Knight可能很强大
由于输入的字符都是大写字母，建立一个大小大于26的num数组对字符串里的字符进行计数
从最后一个Z到A进行遍历，找出最大的价值的字符即可
#include<stdio.h>
#include<string.h>
int main() {
int T, cas = 1, num[27], ans, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
char ss[105];
ans = 0;
scanf("%s",ss);
memset(num, 0, sizeof(num));
for(int i = 0; i < strlen(ss); i++) {
num[ss[i] - 'A' + 1]++;
ans += ss[i] - 'A' + 1;
}
char a = 'Z';
int maxx = num[26] * 26;
for(int i = 25; i > 0; i--) {
if(num[i] * i > maxx) {
maxx = num[i] * i;
a = 'A' + i - 1;
}
}
printf("Case #%d:\n%d\n%c : %d\n",cas++, ans, a, maxx);
}
} E.看我一只穿云箭
简单的高中物理题，直接套公式就可以，零舍一入加上了0.00000004就跟四舍五入等价了
#include<stdio.h>
int main() {
int T, n, cas = 1;
double x, y, v0, ans;
scanf("%d", &T);
while(T--) {
scanf("%lf %lf %lf",&v0, &y, &x);
ans = 2 * x * y * v0 * v0 / (10 * x * x + 10 * y * y);
printf("Case #%d: %.7lf\n", cas++, ans + 0.00000004);
}
return 0;
} F. 兔叽先生和长颈鹿女士
简单的进制转换，给的数据在int范围内，所以只要用格式化输出就可以了
#include<stdio.h>
int main(){
int T, n, cas = 1;
scanf("%d",&T);
while(T--){
int n;
scanf("%d", &n);
printf("Case #%d: %d %o %x\n", cas++, n, n, n);
}
return 0;
} 应出题人要求，写一份出题人原标程
#include<stdio.h>
#include<string.h>
char ch8[10];
char ch16[10];
int main() {
int t, n, temp, count = 1;
scanf("%d", &t);
while(t--) {
int i = -1, j = -1;
scanf("%d", &n);
temp = n;
while(temp) {
++i;
ch8[i] = temp % 8 + '0';
temp /= 8;
}
temp = n;
while(temp) {
++j;
ch16[j] = temp % 16 + '0';
if(ch16[j] > '9') {
ch16[j] = ch16[j] - '9' + 96;
}
temp /= 16;
}
printf("Case #%d: %d ", count++, n);
for(; i >= 0; i--) {
printf("%c",ch8[i]);
}
printf(" ");
for(; j >= 0; j--) {
printf("%c",ch16[j]);
}
printf("\n");
}
return 0;
} G.面积面积
简单的求三角形面积，要注意一个点，输入的数据都是整数，但你答案不一定为整数，如果把三条边都设为int型，小心运算过程中丢失小数部分。
#include<stdio.h>
#include<math.h>
int main() {
int a, b, c, T, cas = 1;
double ans, s;
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &a, &b, &c);
s = a + b + c;
s /= 2.0;
ans = sqrt(s * (s - a) * (s - b) * (s - c));
printf("Case #%d : %.2lf\n", cas++, ans);
}
} H.所有人！都别过来！
对于新生来说这是一道防ac题目，一道模拟题
过程思路已经在代码里面了
#include <stdio.h>
int numa[15], numb[15];
int a, b;
int T, cas;
void getAns(){
int man3 = 1, man2 = 0, man1 = 0, sum = 1;// 当前回合剩下三滴血的奴隶主 两滴血的奴隶主 一滴血的奴隶主 所有奴隶主的人数
for(int i = 0; i < 17; i++){
int cnt = 0;//该回合己方已使用的随从格
int dead = 0;//该回合死亡人数
for(int i = 0; i < a; i++){//己方在场上的原随从经过一次亵渎
if(numa[i]){
cnt++;
numa[i]--;//原随从血量减少
if(numa[i] == 0){
dead++;//该回合己方原随从死亡人数
}
}
}
for(int i = 0; i < b; i++){//敌方在场上的原随从经过一次亵渎
if(numb[i]){
numb[i]--;//原随从血量减少
if(numb[i] == 0){
dead++;//该回合敌方原随从死亡人数
}
}
}
dead += man1;//该回合一血奴隶主死亡
cnt += sum;//该回合己方已使用的随从格加上奴隶主使用的随从格
sum -= man1;//奴隶主人数减去死亡的一血奴隶主人数
man1 = man2;//二血奴隶主变为一血奴隶主
man2 = man3;//三血奴隶主变为二血奴隶主
if(sum > 7 - cnt){//新召唤出来的奴隶主比当前的空的随从格多的情况
man3 = 7 - cnt;
}
else{//新召唤出来的奴隶主比当前的空的随从格少或者刚刚好的情况
man3 = sum;
}
sum = man1+man2+man3;//当前奴隶主人数更新
if(dead == 0){
break;//当前没人死亡 则亵渎结束
}
}
printf("Case #%d:%d\n", cas++, sum);
}
int main(){
scanf("%d", &T);
cas = 1;
while(T--){
scanf("%d %d", &a, &b);
for(int i = 0; i < a; i++){
scanf("%d", &numa[i]);//己方原随从的血量
}
for(int i = 0; i < b; i++){
scanf("%d", &numb[i]);//敌方原随从的血量
}
getAns();
}
return 0;
} I.Everduo与星澈的合奏
一道普通的字符串比较题目，进行计数。
由于字符串长度不大，时间复杂度也不高，可以直接暴力过的，如果追求完美想优化可以使用kmp算法
#include<stdio.h>
#include<string.h>
char a[6000],b[6000];
int main() {
int T,n;
scanf("%d",&T);
while(T--){
int la, lb;
scanf("%d %d", &la, &lb);
getchar();
scanf("%s%s", a, b);
int count = 0;
for(int i = 0 ; i < strlen(a) - strlen(b) + 1; i++){
if(a[i] == b[0]) {
int flag = 1;
for(int j = 0 ; j < strlen(b); j++) {
if(a[i + j] != b[j]) {
flag = 0;
break;
}
}
if(flag) {
count++;
}
}
}
printf("%d\n",count);
}
return 0;
} J.聪明的你
这是一道逗你玩的题目，运用的典故是三姬分金，在三方都很聪明的情况下，第一个人无论有多少钱，都可以在一开始拿全部的钱
#include<stdio.h>
#define ll long long
int main() {
int T, cas = 1;
scanf("%d", &T);
while(T--){
ll n;
scanf("%lld", &n);
printf("Case #%d : %lld 0 0\n", cas++, n);
}
return 0;
} K.征途的开始
这道题没你想象那么复杂，只要高中概率的知识没丢了，或者去推一下概率就可以知道无论第几回合用某个技能，其概率都一样，如果一共有n次释放技能的机会，第a个技能有m次释放机会，那么第a个技能在任意一个回合释放技能的概率都为n/m。
#include<stdio.h>
int main() {
int T, cas = 1;
scanf("%d", &T);
while(T--) {
double ans = 0, num[10];
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lf", &num[i]);
ans += num[i];
}
int a, b;
scanf("%d%d", &a, &b);
if(ans == 0){
printf("Case #%d:0.0000\n", cas++);
} else {
printf("Case #%d:%.4lf\n", cas++, num[b]/ans);
}
}
return 0;
} L. 加减重定义 V1.0
这是一道普通的字符串简单模拟题，也就是四则运算的简单版，因为是简单版，所以代码也很简单
#include <stdio.h>
int main() {
int T, ans, tmp, n, flag, cas = 1;
scanf("%d", &T);
char c;
for (int k = 1; k <= T; k++) {
scanf("%d", &n);
flag = -1;
while (scanf("%d%c", &tmp, &c)) {
if (flag == -1) {
ans = tmp;
} else if (flag) {
ans -= tmp;
} else {
ans += tmp;
}
if (c == '\n') {
break;
} else if (c == '+') {
flag = 1;
} else {
flag = 0;
}
}
printf("Case #%d: %d\n", cas++, ans);
}
} M. 那是你离开了北京的生活
这道题题意很难看出是网络流，是拿来防ak的，是一道最小费用最大流题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
const int maxn = 2 * 1e5 + 5;
const int inf = 0x3f3f3f3f; // 可用memset
int cnt = 0,source,sink;
int head[maxn],dis[maxn],pre[maxn];
bool vis[maxn];
struct node {
int u,v,w,c,nxt;
node() {}
node(int u,int v,int w,int c,int nxt):u(u),v(v),w(w),c(c),nxt(nxt) {}
} e[maxn];
struct video {
int l,r,c,opt;
} vdo[maxn];
void add(int u,int v,int w,int c) {
e[cnt] = node(u,v,w,c,head[u]);
head[u] = cnt++;
e[cnt] = node(v,u,0,-c,head[v]);
head[v] = cnt++;
}
void init(int m,int k) {
cnt = 0;
mem(head,-1);
source = 0;
sink = 2 * m + k + 1;
}
bool spfa() {
mem(vis,false);
mem(dis,inf);
dis[source] = 0;
vis[source] = true;
queue<int>q;
q.push(source);
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = e[i].nxt) {
int v = e[i].v,w = e[i].w,c = e[i].c;
if(w > 0 && ((dis[u] + c) < dis[v])) {
dis[v] = dis[u] + c;
pre[v] = i;
if(!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
return dis[sink] != inf;;
}
int MinCostMaxFlow() {
int full = 0;
int cost = 0;
while(spfa()) {
int minn = inf;
for(int i = sink; i != source; i = e[pre[i]].u) {
minn = min(minn,e[pre[i]].w);
}
for(int i = sink; i != source; i = e[pre[i]].u) {
e[pre[i]].w -= minn;
e[pre[i] ^ 1].w += minn;
}
cost += minn * dis[sink];
full += minn;
}
return cost;
}
int main() {
int T,n,m,k,w,Case = 1;
scanf("%d",&T);
while(T--) {
scanf("%d %d %d %d",&n,&m,&k,&w);
init(m,k);
for(int i = 1; i <= m; i++) {
scanf("%d %d %d %d",&vdo[i].l,&vdo[i].r,&vdo[i].c,&vdo[i].opt);
}
for(int i = 1; i <= m; i++) {
add(i,i + m,1,-vdo[i].c);
add(i + m,sink,1,0);
for(int j = 1; j <= m; j++) {
if(vdo[i].r <= vdo[j].l) {
if(vdo[i].opt != vdo[j].opt) {
add(i + m,j,1,0);
} else {
add(i + m,j,1,w);
}
}
}
}
for(int i = 1; i <= k; i++) {
add(source,i + 2 * m,1,0);
for(int j = 1; j <= m; j++) {
add(i + 2 * m,j,1,0);
}
}
printf("Case #%d: %d\n",Case++,MinCostMaxFlow() * -1);
}
return 0;
}
