A题:银行排队
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 101;
int num[maxn];
int main()
{
int n,ans;
while(~scanf("%d",&n))
{
ans=0;
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
}
sort(num,num+n); //给这个n个人的时间排序
for(int i=n;i>=1;i--) //求总时间
{
ans+=i*num[n-i];
}
printf("%d\n",ans);
}
return 0;
}
B题:绝地求生
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,hp,ans;
void dfs(int hp);
int main()
{
while(~scanf("%d %d %d",&m,&n,&hp))
{
ans=0;
dfs(hp);
printf("%d\n",ans);
}
return 0;
}
void dfs(int hp)
{
if(hp<=0)
{
ans++;
return ;
}
dfs(hp-m);
dfs(hp-n);
}
C题:电子狗的心事
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000001;
int a[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int num,ans;
ans=0;
scanf("%d",&num);
for(int i=1;i<=num;++i)
{
scanf("%d",&a[i]);
}
if(num<=3)
{
printf("regret\n");
continue;
}
/*
else if(num==4)
{
if(a[4]>=a[2] && a[3]<=a[1])
{
ans=4;
printf("%d\n",ans);
}else printf("Catch you\n");
continue;
}
else if(num==5)
{
if(a[5]>=a[3] && a[4]<=a[2])
{
ans=5;
printf("%d\n",ans);
}else if(a[5]+a[1]>=a[3] && a[4]==a[2])
{
ans=5;
printf("%d\n",ans);
}
else printf("Catch you\n");
continue;
}
*/
for(int i=4;i<=num;++i)
{
if(i>=4)
{
if(a[i]>=a[i-2] && a[i-1]<=a[i-3])
{
ans=i;
break;
}
}
if(i>=5)
{
if(a[i-1]==a[i-3] && a[i-2] <= a[i]+a[i-4])
{
ans=i;
break;
}
}
if(i>=6)
{
if(a[i]+a[i-4]>=a[i-2] && a[i-1]+a[i-5]>=a[i-3] && a[i-1]<=a[i-3] && a[i-4]<=a[i-2])
{
ans=i;
break;
}
}
}
if(ans==0){
printf("regret\n");
}else printf("%d\n",ans);
}
return 0;
}
D题:三体——人类的末日之战
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 50;
char map[maxn][maxn];
struct hu{
int x;
int y;
}spaceship[50]; //若干搜飞船的横纵坐标
int copyx[maxn]; //全排列飞船的横坐标
int copyy[maxn]; //全排列飞船的纵坐标
int judge[maxn]; //判断是否已经选择过该搜飞船
int ans,step,h;
void dfs_10(int n);
int min1=0; //路径初始值为99999
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int m,n;
ans=0;
min1=99999;
scanf("%d %d",&m,&n);
for(int i=0;i<m;++i) //读取这个矩阵的信息
{
scanf("%s",map[i]);
}
for(int i=1;i<50;++i) //开始所有的飞船均没有选择过
{
judge[i]=1;
// printf("%d_\n",judge[i]);
}
step=1;
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j){
if(map[i][j]=='W') //保存水滴的坐标
{
spaceship[0].x=i;
spaceship[0].y=j;
}else if(map[i][j]=='S') //保存飞船的坐标
{
spaceship[step].x=i;
spaceship[step].y=j;
step++;
}
}
}
step--; //此时有step搜飞船
/*
for(int i=0;i<=step;++i) //验证水滴与飞船的坐标是否保存正确
{
printf("%d %d\n",spaceship[i].x,spaceship[i].y);
}
*/
copyx[0]=spaceship[0].x; //将水滴的横纵坐标保存在全排列的数组中
copyy[0]=spaceship[0].y;
h=1;
dfs_10(1); //从第一艘飞船开始搜索
/*
for(int i=1;i<50;++i) //开始所有的飞船均没有选择过
{
// judge[i]=1;
printf("%d_\n",judge[i]);
}*/
printf("%d\n",min1);
ans=0;
}
return 0;
}
void dfs_10(int n)
{
if(n>step) //搜索一组排列完毕,开始计算当前路径
{
ans=0; //路径初始值为0
// printf("*******************\n");
for(int i=0;i<step;i++) //从水滴开始,一直到倒数第二艘飞船
{
ans+=abs(copyx[i]-copyx[i+1])+abs(copyy[i]-copyy[i+1]);
// printf("%d(((())))\n",ans);
//将相邻两艘飞行器的横纵坐标之差的和相加
}
/*
if(ans==22){
for(int i=0;i<=step;i++){
printf("**%d %d***\n",copyx[i],copyy[i]);
}
}*/
if(ans<min1) min1=ans; //如果当前的计算值比最小的还小,则储存起来
return ;
}
for(int i=1;i<=step;++i) //从第一艘飞船开始搜索
{
if(judge[i]==1) //如果judge[i]==1,说明没搜过该飞船,则加入排列中
{
judge[i]=0; //表示已经搜索过
copyx[n]=spaceship[i].x; // n代表正在搜索第几艘战舰,即存入当前坐标
copyy[n]=spaceship[i].y;
/*
if(spaceship[i].x==7 && spaceship[i].y==0)
{
printf("woaini\n");
}
*/
++n;
dfs_10(n); //搜索下一艘战舰
n--; //回溯
judge[i]=1; //
}
}
}
E题:豆落谁家
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
double anse,ans;
void dfs(int a,int b,int k);
int main(){
int t,a,b;
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d%d",&a,&b);
anse=ans=0;
dfs(a,b,0);
printf("Case %d:%.6lf %.6lf\n",i,anse,ans);
}
return 0;
}
void dfs(int a,int b,int k){
int tem=a<b?a:b;
if(k>33){
return;
}
if(a==0){
anse+=k*pow(0.5,k);
return;
}
if(b==0){
ans+=pow(0.5,k);
anse+=k*pow(0.5,k);
return;
}
dfs(a-tem,b+tem,k+1);
dfs(a+tem,b-tem,k+1);
}
F:入侵与反击
#include<stdio.h>
#define MAXN 20010
int dp[MAXN], a[MAXN];
int main()
{
int n, i, j, t, temp;
int max, min;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
dp[1] = 1;
// max=5000;
for (i = 2; i <= n; i++)
{
temp = 0;
for (j = 1; j < i; j++)
if (a[i] <= a[j])
if (temp < dp[j])
temp = dp[j];
dp[i] = temp + 1;
}
max = 0;
for (i = 1; i <= n; i++)
if (max < dp[i])
max = dp[i];
min = n - max;
printf("%d\n", min);
}
return 0;
}
G:战争联盟
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXX = 100010;
int fa[MAXX], r[MAXX];
int find(int x)
{
if (fa[x] == x) return fa[x];
int tmp = fa[x];
fa[x] = find(fa[x]);
r[x] = (r[tmp] + r[x]) % 2;
return fa[x];
}
void fun(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fy] = fx;
r[fy] = (r[x] + 1 - r[y]) % 2;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int N, M, x, y;
char res[5];
scanf("%d%d", &N, &M);
for (int i = 0; i <= N; i++) fa[i] = i, r[i] = 0;
while (M--)
{
scanf("%s %d %d", res, &x, &y);
if (res[0] == 'A')
{
if (find(x) == find(y))
{
if (r[x] == r[y])
printf("Belong to same group.\n");
else
printf("Belong to different group.\n");
}
else
printf("Not sure yet.\n");
}
else
fun(x, y);
}
}
return 0;
}
H:贴瓷砖
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[255][255];
char s[255][255];
int num[255];
int min(int a, int b, int c) {
if (a>b)
a = b;
if (a>c)
a = c;
return a;
}
int main() {
int n, i, j, flag = 0;
while (~scanf("%d", &n), n) {
memset(dp, 0, sizeof(dp));
memset(num, 0, sizeof(num));
if (flag)
printf("\n");
flag++;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
cin >> s[i][j];
for (i = n - 1; i >= 0; i--){
for (j = n - 1; j >= 0; j--){
if (s[i][j] - '0'){
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]) + 1;
}
for (int k = 2; k <= dp[i][j]; ++k){
num[k]++;
}
}
}
for (i = 2; i <= n; ++i){
if (num[i]){
printf("%d %d\n", i, num[i]);
}
}
}
return 0;
}
I:正则表达式
#include<stdio.h>
int match(char *regexp, char *text);
int regexpstar(int c, char *regexp, char *text);
int regexpask(int c, char *regexp, char *text);
int regexpall(int c, char *regexp, char *text);
int match(char *regexp, char *text) {
if (regexp[0] == '\0'&&text[0] == '\0')
return 1;
if (regexp[0] != text[0] && regexp[0] != '.'&®exp[1] != '*'&®exp[1] != '?')
return 0;
if (regexp[1] == '*') {
if (regexp[2] != '?')
return regexpstar(regexp[0], regexp + 2, text);
else
return regexpall(regexp[0], regexp + 3, text);
}
if (regexp[1] == '?') {
return regexpask(regexp[0], regexp + 2, text);
}
if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
return match(regexp + 1, text + 1);
return 0;
}
int regexpstar(int c, char *regexp, char *text){
do {
if (match(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
int regexpask(int c, char *regexp, char *text) {
int flag = 0;
do {
if (match(regexp, text))
return 1;
flag++;
if (flag == 2)
return 0;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
int regexpall(int c, char *regexp, char *text) {
do {
if (match(regexp, text))
return 1;
if (regexp[0] == text[0])
return 0;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
int main() {
char s[105], p[105];
while (scanf("%s%s", s, p)) {
if (s[0] == '0'&&p[0] == '0')
break;
if (match(p, s))
printf("true\n");
else
printf("false\n");
}
return 0;
}
J:
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define MAXN 12
using namespace std;
struct node {
int x;
int y;
int step;
};
struct note {
int x;
int y;
};
int L, R, C;
char maze[35][35];
int book[35][35];
int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
node re, ne;
vector<note>AA[12];
int bfs(int sx, int sy, int ex, int ey) {
queue<node>res;
re.x = sx, re.y = sy;
re.step = 0;
book[sx][sy] = 1;
res.push(re);
while (!res.empty()) {
re = res.front();
res.pop();
if (re.x == ex&&re.y == ey) {
return re.step;
}
if (maze[re.x][re.y] - '0'>0 && maze[re.x][re.y] - '0'<=C) {
int numb = maze[re.x][re.y] - '0';
for (vector<note>::iterator it = AA[numb].begin(); it != AA[numb].end(); it++) {
ne = re;
ne.x = it->x;
ne.y = it->y;
if (book[ne.x][ne.y] != 1) {
book[ne.x][ne.y] = 1;
ne.step = ne.step + 1;
res.push(ne);
}
}
}
for (int i = 0; i < 4; i++) {
ne = re;
ne.x += dir[i][0];
ne.y += dir[i][1];
if (ne.x >= 0 && ne.x < L&&ne.y >= 0 && ne.y < R&&book[ne.x][ne.y] != 1 && maze[ne.x][ne.y]!= '#') {
book[ne.x][ne.y] = 1;
ne.step = ne.step + 1;
res.push(ne);
}
}
}
return 0;
}
int main() {
while (~scanf("%d%d%d", &R, &L, &C), L + R + C) {
memset(book, 0, sizeof(book));
for (int i = 0; i < MAXN;i++)
AA[i].clear();
int sx, sy, ex, ey;
note fres;
for (int i = 0; i < L; i++) {
scanf("%s", maze[i]);
for (int j = 0; j < R; j++) {
fres.x = i, fres.y = j;
if (maze[i][j] == 'S') //入口
sx = i, sy = j;
else if (maze[i][j] == 'E') //出口
ex = i, ey = j;
else if (maze[i][j] == 'M')//怪物
maze[i][j] = '#';
else if (maze[i][j] - '0'>0 && maze[i][j] - '0' <= C) {//传送门类型
int numb = maze[i][j] - '0';
AA[numb].push_back(fres);
}
}
}
int ans = bfs(sx, sy, ex, ey);
if (!ans)
printf("Trapped!\n");
else
printf("%d\n", ans);
}
return 0;
}
K:数字拼图
#include<stdio.h>
#include<string.h>
int check(int *p, int n) {
int i, j, flag = 0;
for (i = 1; i < n*n - 1; i++)
for (j = 0; j < i; j++)
if (p[j] > p[i])
flag++;
flag %= 2;
return flag;
}
int main() {
int N;
int a[20];
while (~scanf("%d", &N), N) {
memset(a, 0, sizeof(a));
for (int i = 0; i < N*N; i++) {
scanf("%d", &a[i]);
}
if (check(a, N))
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
M:FeHead的项目