目录
CSU 内部题 小Y的彩色立方体
题目：
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
char a1,a2,a3,b1,b2,b3,e;
int cas=1;
while(cin>>e>>e>>a1>>a2>>a3>>e>>e>>e>>b1>>b2>>b3>>e)
{
cout<<"Case "<<cas++<<": ";
if(a1>a3)swap(a1,a3);
if(a2>a3)swap(a2,a3);
if(a1>a2)swap(a1,a2);
if(b1>b3)swap(b1,b3);
if(b2>b3)swap(b2,b3);
if(b1>b2)swap(b1,b2);
if(a1==b1&&a2==b2&&a3==b3)
cout<<"Same "<<a1<<a2<<a1<<a2<<a3<<a3<<endl;
else cout<<"Different"<<endl;
}
return 0;
}CSU 内部题 小z的远古讯息
题目：
代码：
#include<iostream>
#include<stdio.h>>
using namespace std;
char c[400][400];
int num[52];
int getrank(char c)
{
if(c>='a')return c-'a';
return c-'A'+26;
}
char getchar(int r)
{
if(r<26)return 'a'+r;
return 'A'+r-26;
}
int main()
{
int t,n;
cin>>t;
while(t--)
{
scanf("%d",&n);
for(int i=0;i<52;i++)num[i]=0;
for(int i=0;i<n;i++)
{
scanf("%s",c[i]);
for(int j=0;j<n;j++)num[getrank(c[i][j])]++;
}
int maxx=0,key=0;
for(int i=0;i<52;i++)
{
if(maxx<num[i])
{
maxx=num[i];
key=i;
}
}
char ch=getchar(key);
int up=401,down=-1,left=401,right=-1;
for(int i=0;i<n;i++) for(int j=0;j<n;j++)if(c[i][j]==ch)
{
if(up>i)up=i;
if(down<i)down=i;
if(left>j)left=j;
if(right<j)right=j;
}
for(int i=up;i<=down;i++)
{
for(int j=left;j<=right;j++)
{
if(c[i][j]==ch)printf("%c",ch);
else printf(" ");
}
printf("\n");
}
}
return 0;
}CSU 内部题 简单加密（2017年院赛D题）
题目：
简单加密
Description:
小A和小B之间有数字信息来往，但是小A担心自己发送给小B的私密信息泄露被他人获取，于是他打算研究一个简单的加密方法只有自己和小B看得懂。小A给小B发送的信息保证都是1~9之间的数字，小A通过奇数位上的数字表示个数，对应的下一个偶数位的数字表示对应个数的数字来加密（比如：2635表示两个6连着3个5加密之后就是66555），如果最后一位是奇数位置结尾个数表示n，那么连着的加密串就是n个*（比如263加密后就是66***）。
Input：
第一行输入一个正整数T表示数据组数（T<=1000)
接下来T行每行输入一个字符串表示小A要发送给小B的信息（字符串长度不超过100）
Output：
对于每组数据输出一行小A信息加密之后的字符串
Sample Input：
2
2635
263
Sample Ouput：
66555
66***
标程：
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
int T ;
char str[105] , ans[1005];
scanf("%d" , &T);
while(T--){
scanf("%s" , str);
int len = strlen(str);
int pos = 0;
for(int i=0 ; i<len ; i+=2){
int cnt = str[i]-'0';
char ch;
if(i+1 >= len) ch='*';
else ch=str[i+1];
for(int j=0 ; j<cnt ; j++) ans[pos++] = ch;
}
ans[pos] = '\0';
printf("%s\n" , ans);
}
return 0;
}我的代码：
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char c[101];
int t;
cin>>t;
while(t--)
{
cin>>c;
int k=0,l=strlen(c);
while(k<=l-2)
{
for(int i=0;i<c[k]-'0';i++)cout<<c[k+1];
k+=2;
}
if(k==l-1)for(int i=0;i<c[k]-'0';i++)cout<<'*';
cout<<endl;
}
return 0;
}CSU 内部题 守望者的逃离（2017年院赛E题）
题目：
Description：
恶魔猎手尤迪安野心勃勃，她背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。
现在一直守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为正数秒。距离单位为米(m)。
Input：
第一行一个整数t，代表有t组数据，接下来t行，每一行包括空格隔开的三个非负整数M, S, T。
Output：
对于每一组数据输出两行，第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。
SampleInput：
1
39 200 4
SampleOutput：
No
197
标程：
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
int m, s, t, times;
cin>>times;
while(times--){
cin >> m >> s >> t;
int m_n=m, s_n=0, t_n=0;
while (t_n < t&&s_n < s){
if (m_n >= 10)
m_n -= 10, s_n += 60,++t_n;
else if (m_n>=6){
if (s - s_n <= 17||t-t_n==1)
++t_n, s_n += 17;
else
m_n -= 6, s_n += 60, t_n += 2;
}else if (m_n >= 2){
if (t - t_n <= 2)
s_n += 17, ++t_n;
else if (s - s_n <= 34)
++t_n, s_n += 17;
else
m_n -= 2, s_n += 60, t_n += 3;
}else{
if (t - t_n <= 6)
s_n += 17, ++t_n;
else if (s - s_n <= 102)
++t_n, s_n += 17;
else
t_n += 7, s_n += 120;
}
}
cout << ((s_n >= s) ? ("Yes") : ("No")) << endl << ((s_n >= s) ? t_n : s_n)<<endl;
}
return 0;
}因为题目没写m,s,t的范围，所以我考虑的是三个数都是int范围内的任意数，也就是说我提交的是一个O（1）的算法，原理是在O（1）的时间内将问题转化成2个子问题，而这2个中的参数都小于某个很小的常数。这个方法，和POJ 1915 Knight Moves DFS、BFS_nameofcsdn的博客-CSDN博客里面的方法如出一辙。
我的代码：
#include<iostream>
using namespace std;
int time2(int m,int s)
{
if(s<=0)return 0;
if(m>=10)return time2(m-10,s-60)+1;
int k=time2(m+4,s)+1;
if(k>(s+16)/17)k=(s+16)/17;
return k;
}
int time(int m,int s)
{
int k=m/10;
m-=k*10;
if(s<=k*60)return (s+59)/60;
if(k)return time(m,s-k*60)+k;
k=s/120-1;
if(k>0)return time(m,s-k*120)+k*7;
return time2(m,s);
}
int len(int m,int t)
{
if(t==0)return 0;
int k=m/10;
m-=k*10;
if(t<k)return t*60;
if(k)return len(m,t-k)+k*60;
k=t/7-1;
if(k>0)return len(m,t-k*7)+k*120;
k=len(m+4,t-1);
if(k<t*17)k=t*17;
return k;
}
int main()
{
int T,m,s,t,ans;
cin>>T;
while(T--)
{
cin>>m>>s>>t;
ans=time(m,s);
if(ans<=t)cout<<"Yes\n"<<ans<<endl;
else cout<<"No\n"<<len(m,t)<<endl;
}
return 0;
}其实函数time和time2是不用分离的，但是为了更好的防止死循环，还是分开写了，直接把time2的代码复制到time里面调用time2地方应该也是正确的。
CSU 内部题 最大异或和（2017年院赛H题）
题目：
Description：
小A帮小B解决了在一串数字中找到一段连续的数字和最大这个问题，为了让小B不局限于这么一个简单的问题当中能够举一反三，小A让小B思考同样的道理如何能找到一段连续的数字它们的异或和最大呢？
Input：
输入样例组数正整数T(T<=1000)
每组样例输入一个正整数n，表示数字的个数(n<=100000)
接下来一行输入n个正整数a0,a1,....,a(n-1) (任意ai<2^31)
Output：
每组样例输出一个答案表示最大的一段异或和的值
Sample Input：
2
3
4 8 5
3
4 8 16
Sample Output：
13
28
标程：
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define max(a,b) a>b?a:b
int bit[32];
struct Node{
Node *lson,*rson;
Node(){lson=rson=NULL;}
}*root;
void init()
{
root = new Node(); bit[0] = 1;
for(int i=1 ; i<32 ; i++) bit[i] = bit[i-1]<<1;
}
void insert(int x)
{
Node *cur = root;
for(int i=31 ; i>=0 ; i--){
if(bit[i]&x){
if(!cur->rson) cur->rson = new Node();
cur = cur->rson;
}else{
if(!cur->lson) cur->lson = new Node();
cur = cur->lson;
}
}
}
int match(int x)
{
Node *cur = root;
int ans = 0;
for(int i=31 ; i>=0 ; i--){
if(bit[i]&x){
if(cur->lson) cur = cur->lson , ans = ans|bit[i];
else cur = cur->rson;
}else{
if(cur->rson) cur = cur->rson , ans = ans|bit[i];
else cur = cur->lson;
}
}
return ans;
}
int main()
{
int n , x , cur , T , ans;
scanf("%d" , &T);
while(T--){
init();
insert(0); ans = cur = 0;
scanf("%d" , &n);
for(int i=0 ; i<n ; i++){
scanf("%d" , &x);
cur = cur^x ;
ans = max(ans , match(cur));
insert(cur);
}
printf("%d\n" , ans);
}
return 0;
}POJ 内部题 表示大整数
| 描述 | |
| 若一个数太大，人们很难正确读出这个数。例如1亿=100000000，很容易就把8个0数成7个或9个0，从而读错。 为了避免这种误差，提出一种方法，写数字的时候，每隔一定长度k，加一个逗号。 例如，按照西方读数的习惯，每隔三位写一个逗号，1亿=100,000,000能很快读出来100million。 再例如，按照中国读数的习惯，每隔四位写一个逗号，1亿=1,0000,0000能很快读出来1亿。 现在给你一个数n，以及逗号的间隔长度k，请写出用逗号隔开之后的数。 | |
| 关于输入 | |
| 第一行一个数t(t<=10)，表示数据组数。 接下来t行，每行两个整数，n和k，用空格隔开。其中n不超过int的表达范围，1<=k<=5。 | |
| 关于输出 | |
| 一共t行，每行为一个用逗号隔开之后的数。 | |
| 例子输入 | |
3 12345 3 12345 1 -1234 2 | |
| 例子输出 | |
| 12,345 1,2,3,4,5 -12,34 |
如果把k映射到10^k，然后利用整数的除法，需要注意一个问题：0的问题
比如123405 2，结果应该是12,34,05而不是12,34,5
还有一种思路是根本不读入整数，而是读入字符串，然后把逗号插进去
代码：
#include<stdio.h>
#include<string.h>
int main()
{
int t, i, k, j;
char c[12];
scanf("%d", &t);
for (i = 1; i <= t; i++)
{
scanf("%s %d", &c, &k);
int low = 0, high = strlen(c);
if (c[0] == '-')printf("%c", c[low++]);
for (j = low; j < high; j++)
{
printf("%c", c[j]);
if (high - j>1 && (high - 1 - j) % k == 0)printf("%c", ',');
}
printf("\n");
}
return 0;
}POJ 内部题 IBM编码(字符串)
| 描述 | |
| 在“2001太空漫游”这部电影中，一艘宇宙飞船飞往木星。长途飞船上除了飞行员，还有三名处在冬眠状态的科学家。飞船是由智能计算机HAL控制。但在飞行过程中，HAL的行为越来越奇怪，甚至开始杀死所有船员，…... 电影上映后，变得非常流行，有一些讨论，如"HAL"实际上意味着什么。一些人认为它可能是“启发式算法（Heuristic Algorithm）”的缩写。但最流行的解释是：如果将HAL的每一个字母更换成其在ASCII字母表中的继任者，你得到的会是…IBM，也就是每一个字母用其后继字母替代。 现在，我们也采取同样的编码方式对信息进行表示。 即对于给定的字符串，把其中从a-y、A-Y的字母用其后继字母替代，把z和Z用a和A替代。只改变字符串中的字母，字符串中的其他字符保持不变。 | |
| 关于输入 | |
| 第一行是字符串的数目n(n<=10)，用gets(s)读取，再用n=atoi(s)获得整数数值 其余n行每行一个可能含空格的字符串，每个字符串长度小于50个字符，用gets(s)方式读取每行字符串 | |
| 关于输出 | |
| 输出有n行，每行是一个字符串的编码结果 | |
| 例子输入 | |
4 hello how are you? are you ready? yes, I'm ready! OK, let's go! | |
| 例子输出 | |
ifmmp ipx bsf zpv? bsf zpv sfbez? zft, J'n sfbez! PL, mfu't hp! | |
| 提示 | |
| 避免gets和scanf在使用时的冲突：用n=atoi(s)把字符串s转换为整数，函数atoi()定义在头文件stdlib.h中 |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int t, i, j;
char c[60];
gets(c);
t = atoi(c);
for (i = 1; i <= t; i++)
{
gets(c);
for (j = 0; j < strlen(c); j++)
{
if(c[j]>='a'&&c[j]<'z'||c[j]>='A'&&c[j]<'Z')printf("%c", c[j]+1);
else if (c[j] == 'z' || c[j] == 'Z')printf("%c", c[j] -25);
else printf("%c", c[j]);
}
printf("\n");
}
return 0;
}POJ 内部题 医院排号
| 描述 | |
| 北大校医院最近更新了自己的网上排号系统，考虑到病人的病情程度不同，需要优先考虑病情较重的病人，病情相同的情况下需要把先在网上挂号的病人排在前面。现在给出了请求在同一天看病的n个病人网上挂号的顺序，但是校医院一天只能接收k个病人，请输出校医院当天接收的所有病人的看病顺序。 | |
| 关于输入 | |
| 第一行：一个整数t，表示数据的组数： 对于每组数据，分别有两行： 第一行：两个整数n 和k (k不一定小于n)，表示请求在同一天看病的病人有n个，医院当天只能接受k个病人 第二行：n个整数，第i个整数表示第i个在网上挂号的病人的病情严重程度 | |
| 关于输出 | |
| 对每组数据输出两行： 第一行：一个整数m（m<=k），表示医院当天实际接受的病人的个数 第二行：一个整数序列，包含m个整数，用空格隔开，最后一个整数之后是一个换行符，表示医院当天看病的安排，第i个整数表示医院当天接收的第i个病人在原先挂号序列当中的序号。 | |
| 例子输入 | |
2 5 3 2 3 4 7 4 6 2 5 10 4 6 9 7 | |
| 例子输出 | |
3 4 3 5 2 2 5 | |
| 提示 | |
| 例子输入输出中一共有两组数据，第一组数据表示当天有5个病人在网上挂号，按照挂号时间先后排列，这五个人的病情程度分别是2，7，4，3，4。同时，医院当天只能接收3个病人。对于第一组数据，医院当天只接收了3个病人，分别是第二个，第三个和第五个（之前5个病人按照病情严重程度排列顺序是4，3，5，2，1）。对第二组数据，严重程度最高的是第2个人，其次是第五个。 建议使用结构类型描述挂号信息。 |
#include<stdio.h>
int main()
{
int t, i, n, k, num[1000],j;
scanf("%d", &t);
for (i = 1; i <= t; i++)
{
scanf("%d%d", &n, &k);
for (j = 1; j <= n; j++)scanf("%d", &num[j]);
if (k > n)k = n;
printf("%d\n", k);
while (k--)
{
int ans = 1;
for (j = 2; j <= n; j++)if (num[ans] < num[j])ans = j;
printf("%d%s", ans, k ? " " : "\n");
num[ans] = 0;
}
}
return 0;
}POJ 内部题 铺地板
| 描述 | |
| 你是一名室内装潢工程队的配料员。你的伙伴们喜欢采用“之”字型（对角线）的顺序方式给方阵型地面铺大理石地砖，图案如下： 1 2 6 7 15 3 5 8 14 16 4 9 13 17 22 10 12 18 21 23 11 19 20 24 25 这里，1-25按方阵的对角线顺序放置。 学了 C 语言以后，你决定编写一个程序，帮助你的同伴生成这样的图形。 | |
| 关于输入 | |
| 地砖方阵的大小N(如：一共25块地砖，由于是正方形阵，则N为5) | |
| 关于输出 | |
| 1到N*N这些数所构成的“之字形”方阵（二维数组），同一行数之间用一个空格隔开，每N个数为一行，共N行。 | |
| 例子输入 | |
4 | |
| 例子输出 | |
1 2 6 7 3 5 8 13 4 9 12 14 10 11 15 16 |
直接把第i行第j列的数求出来即可
代码：
#include<stdio.h>
int f(int i, int j,int n)
{
if (i + j > n + 1)return n*n+1-f(n + 1 - i, n + 1 - j, n);
int s = (i + j - 2)*(i + j - 1) / 2;
if ((i + j) % 2)return s+i;
return s + j;
}
int main()
{
int i,j,n;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
for (j = 1; j < n; j++)printf("%d ", f(i, j, n));
printf("%d\n", f(i, n, n));
}
return 0;
}POJ 内部题 整数删除若干数字后的最小数
| 描述 | |
| 给定一个正整数，从这个正整数中删除若干个数字，可以得到一个新的整数。一般而言，采用不同的删除方案，可以得到不同的整数。求所有可能的删除方案产生的最小的整数。 例如： 1.对于正整数12345，删除3个数字后产生的最小整数为12； 2.对于正整数543212345，删除5个数字后产生的最小整数为1234； 3.对于正整数5432102345，删除5个数字后产生的最小整数为2345； 4.对于正整数137313731373137，删除5个数字后产生的最小整数为1131373137； 5.对于正整数132304，删除5个数字后产生的最小整数为0。 | |
| 关于输入 | |
| 输入有1行。其中包含两个数： 第一个数是一个正整数m，表示将要被删除数字的正整数。m的位数小于100。（对于数字123，其位数为3） 第二个数也是一个正整数k，表示要从第一个数中删除几个数字。两者之间用空格间隔开。 且保证输入的k小于m的位数。 | |
| 关于输出 | |
| 输出有一行。其中只有一个整数，即：删除若干数字后产生的最小整数。 | |
| 例子输入 | |
137313731373137 5 | |
| 例子输出 | |
1131373137 | |
| 提示 | |
| 1.输入的正整数m的位数可能会很长，超出一个整型变量的表示范围。 2.如果删除若干数字后产生了一个首数字为0的非零整数，则在输出时不能输出这些0字符。例如，对于正整数5432102345，删除5个数字后产生的最小整数为02345，但在输出时只能输出2345。 3.如果删除若干数字后产生的整数的值等于0，则只需要输出0。 |
如果不追求效率的话，比较简单的方式是每次删除1个数字，循环k次就直接得到结果。
如果追求效率的话，删除这k个数字不应该独立进行，应该从左往右依次进行。
方案一：k次独立删除1个数字
只需要寻找所有相邻的数字中，第一次出现降低的地方即可。
比如题目中的137313731373137，第一次出现降低的地方就是最前面的1373中的73
必须是严格降低，对于连续的相等的2个数字，直接忽略即可（而且也必须这样）
找到这种组合，删掉左边的数字即可
代码：
#include<stdio.h>
#include<string.h>
int main()
{
char c[105];
int k, len, d, i;
scanf("%s %d", &c, &k);
len = strlen(c);
while (k--)
{
d = len - 1;
for (i = 1; i < len; i++)
{
if (c[i] < c[i - 1])
{
d = i - 1;
break;
}
}
for (i = d; i < len - 1; i++)c[i] = c[i + 1];
len--;
}
i = 0;
while (c[i] == '0'&&i<len)i++;
if (i == len)printf("0");
else while (i < len)printf("%c", c[i++]);
return 0;
}方案二：从左往右依次删除k个数字
从左往右扫描的时候需要注意的是，删掉1个数字之和，指针不仅不能前进，而且还需要回溯。
比如对于相邻的3位abc，发现b>c然后删掉b之和，下一步应该是比较a和c的大小
但是这个比较的工作必须由循环的下一次执行来完成，否则就无穷无尽了。
所以这里只需要i-=2即可。
同时，如果最开始就删掉bc中的b，而b就是最左边的数字，这个时候就不能再比较ac了，因为根本没有ac，强行比较会数组溢出。这种情况只需要continue即可，当然，也可以像下面这样做。
整体代码和方案一里面的差不多
代码：
#include<string.h>
int main()
{
char c[105];
int k, len, d, i, j;
scanf("%s %d", &c, &k);
len = strlen(c);
for (i = 1; i < len && k>0; i++)
{
if (i && c[i] < c[i - 1])
{
for (j = i; j < len; j++)c[j - 1] = c[j];
i-=2, len--, k--;
}
}
len -= k;
i = 0;
while (c[i] == '0'&&i<len)i++;
if (i == len)printf("0");
else while (i < len)printf("%c", c[i++]);
return 0;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
