有问题可以评论或者加我QQ478985071提出,感谢!
习题集链接:
https://acm.ecnu.edu.cn/contest/365/
本文将收录习题集中所有习题的题解,更新看心情,学期前更完,题号按照顺序排序,点目录直达。
1001. 进制转换
https://acm.ecnu.edu.cn/contest/365/problem/1001/
题解
这题还用题解?
10转n进制,短除法倒序向上排。开一个table记录0~9 A~Z,对应0~36的数字。
如果考虑使用栈这一数据结构,其实更简单。
短除入栈,最后逐个弹出输出即可。
代码
#include <iostream>
#include <stack>
using namespace std;
int main(){
char table[36] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
stack<char> s;
int T, N, R;
cin>>T;
for(int i = 0; i < T; i++){
cin>>N>>R;
int flag = 0;
if(N<0) {N*=-1; flag = 1;}
while(N){
int tmp = N%R;
s.push(table[tmp]);
N/=R;
}
if(flag) cout<<'-';
while(!s.empty()){
cout<<s.top();
s.pop();
}
cout<<endl;
}
return 0;
}
1002. 按数据中1的位数排序
https://acm.ecnu.edu.cn/contest/365/problem/1002/
题解
这题考察的知识点大体上有三个,类的定义,cmp的书写,和计算1的个数。
一个一个说明,这里的数字可以抽象成一个含有两个成员的结构体类型。数字本身,和含1的个数。用定义的结构体类型去开数组,然后按照成员写cmp函数,上学期写过很多类似的题,应该不难想到。
cmp的书写,谨记C++的库函数sort和C库函数qsort不一样,具体sort的用法可以百度,这里不赘述。
然后是计算1的个数,我这里提供两种思路。第一种,对于正数,直接模2,碰到1令计数器++;对于负数,和MAX_LONGLONG+1做加法,或者异或,通过溢出达到取补码的效果,再模2算1的个数。但这里会涉及到溢出的妙用,可能在一些编译器上会报警。
第二种,通过判断和1,2,4,8……按位与的结果累加计数器,这里不用考虑正负数,直接用位运算就可以解决,因此更推荐使用这种做法。
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Num{
long long n;
int cntO;
}Num;
bool cmp(Num A, Num B){
if(A.cntO != B.cntO) return A.cntO > B.cntO;
else return A.n < B.n;
}
int count_One(long long number){
int cnt = 0;
long long test = 1;
for(int i = 0; i < 64; i++){
if(number & test)
cnt++;
test <<= 1;
}
return cnt;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N; cin>>N;
Num nums[10001];
for(int j = 0; j < N; j++){
cin>>nums[j].n;
long long tmp = nums[j].n;
nums[j].cntO = count_One(nums[j].n);
}
sort(nums, nums+N, cmp);
cout<<"case #"<<i<<':'<<endl;
for(int j = 0; j < N; j++)
cout<<nums[j].n<<' ';
cout<<endl;
}
return 0;
}
1003. 神秘信息
https://acm.ecnu.edu.cn/contest/365/problem/1003/
题解
善用下标映射。char的范围是-128~127,对于普通字符,可以通过开一个128长度的数组,用字符变量作为数组的下标,对应的值就是位权。
其他的参照老师的PPT即可。
代码
#include <iostream>
#include <string.h>
using namespace std;
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
char s[61] = {'\0'};
cin>>s;
int table[256];
for(int j = 0; j < 256; j++) table[j] = -1;
table[s[0]] = 1;
int flag = 1;
int R = 1;
int length = strlen(s);
for(int j = 1; j < length; j++){
if(table[s[j]] == -1){
if(flag) {table[s[j]] = 0; flag = 0; R++;}
else table[s[j]] = R++;
}
}
if(R == 1) R = 2;
long long result = 1;
for(int j = 1; j < length; j++){
result = result*R + table[s[j]];
}
cout<<"case #"<<i<<':'<<endl<<result<<endl;
}
return 0;
}
1004. 内存显示
https://acm.ecnu.edu.cn/contest/365/problem/1004/
题解
不知道这题有啥意义,直接输出内存不就行了?可能就是考如何输出内存吧,一般情况用不到这些,还是记一下。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solveint(int n)
{
int c = sizeof(n);
unsigned char *p = (unsigned char *)&n;
while (c--)
printf("%02x ", *p++);
printf("\n");
}
void solvedouble(double d)
{
int c = sizeof(d);
unsigned char *p = (unsigned char *)&d;
while (c--)
printf("%02x ", *p++);
printf("\n");
}
int main()
{
char s[31];
while (scanf("%s", s) != EOF)
if (strchr(s, '.') == 0)
solveint(atoi(s));
else
solvedouble(atof(s));
return 0;
}
1005. 八进制小数(我自己也没懂)
https://acm.ecnu.edu.cn/contest/365/problem/1005/
题解
很难,以我现在的能力说不清楚,还是看ppt吧。
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N=1005;
char str[N];
char dest[N];
int main()
{
int T;
cin>>T;
for(int m = 0; m < T; m++){
int i,j,k,tmp;
cin>>str;
k=0;
memset(dest,0,sizeof(dest));
int len=strlen(str);
for(i=len-1;i>1;i--){
int num=str[i]-'0';
for(j=0;j<k || num!=0;j++){
tmp=10*num+(j<k?dest[j]-'0':0);
dest[j]=tmp/8+'0';
num=tmp%8;
}
k=j;
}
printf("case #%d:\n0.%s\n", m,dest);
}
return 0;
}
1006. 二进制位不同的个数
https://acm.ecnu.edu.cn/contest/365/problem/1006/
题解
俩字,异或。
代码
#include <iostream>
using namespace std;
int f(int x, int y){
int z = x^y;
int cnt = 0;
do{
if(z%2) cnt++;
z /= 2;
}while(z>0);
return cnt;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int x, y;
cin>>x>>y;
cout<<f(x, y)<<endl;
}
return 0;
}
1007. 非重复二进制串
https://acm.ecnu.edu.cn/contest/365/problem/1007/
题解
这题的核心是使用两个变量作为历史记录,与找最大值是一个做法。理解一下历史记录last,maxCnt变量的用法。
还有stack的应用,转R进制进出栈太香了,强烈建议学习STL。
代码
#include <iostream>
#include <stack>
using namespace std;
stack<int> dTob(int a){
stack<int> s;
int table[2] = {0, 1};
while(a){
s.push(table[a%2]);
a /= 2;
}
return s;
}
int longestSubStr(stack<int> s){
int cnt = 0;
int maxCnt = 0;
int last = -1;
while(!s.empty()){
if(s.top() != last) cnt++;
else {
if(maxCnt<cnt) maxCnt = cnt;
cnt = 1;
}
last = s.top();
s.pop();
}
if(maxCnt<cnt) maxCnt = cnt;
return maxCnt;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
cout<<"case #"<<i<<':'<<endl;
int n;
cin>>n;
stack<int> s(dTob(n));
cout<<longestSubStr(s)<<endl;
}
return 0;
}
1008. 数据密度
https://acm.ecnu.edu.cn/contest/365/problem/1008/
题解
gcd应该不用说了吧,辗转相除或者暴力搜索都行。
1的个数参见1002,两种方法都行。
代码
#include <stdio.h>
#include <string.h>
int gcd(int m, int n){
for (int i = m; i >= 1; i--)
if (m % i == 0 && n % i == 0)
return i;
}
int getOne(char c){
int cnt = 0;
if(c<0){
cnt++;
c ^= 128;
}
while(c){
if(c%2) cnt++;
c /= 2;
}
return cnt;
}
int main(){
int n;
scanf("%d", &n);
getchar();
for(int i = 0; i < n; i++){
char str[125] = {'\0'};
char ch;
int index = 0;
while((ch = getchar()) != '\n')
str[index++] = ch;
int length = strlen(str);
int oneDigits = 0;
for(int j = 0; j < length; j++)
oneDigits += getOne(str[j]);
int totalDigits = length*8;
int g = gcd(oneDigits, totalDigits);
oneDigits /= g;
totalDigits /= g;
printf("%d/%d\n", oneDigits, totalDigits);
}
return 0;
}
1009. QR Code
https://acm.ecnu.edu.cn/contest/365/problem/1009/
题解
STL推广题,不用STL不会做系列。
500多位,用数组增增减减左移右移?是我我肯定不干。
stack和vector两个配合起来用,真的舒服兄弟。
需要注意的是如何把分出来的n位(n=1,2,3)字符串转化为二进制码,这个其实挺简单的,转的时候塞进stack里,再把stack里的东西一个一个弹到vec底部即可。
注意传参要传地址,区分形参和实参。
代码
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
void strToB(stack<int> *s, vector<int> *vec, char *str, int start, int end){
int length = end - start + 1;
int num = 0;
for(int i = start; i <= end; i++)
num = num * 10 + str[i] - 48;
for(int i = 0; i < length*3+1; i++){
if(num <= 0) s->push(0);
else{
s->push(num%2);
num /= 2;
}
}
while(!s->empty()){
vec->push_back(s->top());
s->pop();
}
}
int main(){
stack<int> s;
vector<int> vec;
char str[505] = {'\0'};
cin>>str;
int length = strlen(str);
int tmp = length;
for(int i = 0; i < 10; i++){
if(tmp <= 0) s.push(0);
else{
s.push(tmp%2);
tmp /= 2;
}
}
while(!s.empty()){
vec.push_back(s.top());
s.pop();
}
int start = 0;
int end = 2;
if(length - end < 2) {
end = length - 1;
strToB(&s, &vec, str, start, end);
}
else{
while(end < length){
strToB(&s, &vec, str, start, end);
start += 3;
end += 3;
if(length - end < 2) {
end = length - 1;
strToB(&s, &vec, str, start, end);
break;
}
}
}
cout<<"0001";
vector<int>::iterator it = vec.begin();
for(; it != vec.end(); it++)
cout<<*it;
cout<<endl;
return 0;
}
1010. 平衡三进制
https://acm.ecnu.edu.cn/contest/365/problem/1010/
题解
被我找到投机取巧的方法了,同理字母表映射,字符作为下标。重点理解下面三句语句。
table['0'] = 0; table['1'] = 1; table['-'] = -1;
然后秒了。
代码
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
int main(){
int T;
cin>>T;
int table[256] = {0};
table['0'] = 0; table['1'] = 1; table['-'] = -1;
for(int i = 0; i < T; i++){
cout<<"case #"<<i<<":"<<endl;
char str[69] = {'\0'};
cin>>str;
int length = strlen(str);
int num = 0;
for(int j = 0; j < length; j++)
num = num*3 + table[str[j]];
cout<<num<<endl;
}
return 0;
}
1011. 二进制数据压缩
https://acm.ecnu.edu.cn/contest/365/problem/1011/
题解
STL推广题。范围肯定是longlong,我直接开ull了。转二进制码的时候塞进栈里,一个一个弹出,碰到1开始计数,碰到0停下,计数超过2处理一下,否则直接弹出到vector里。碰到0也直接弹出到vector里。
处理方法:开个tmp栈,把cnt计数器转成2进制,进栈出栈弹到vector里。
全程就是stack和vector的配合使用,赶紧学,不学血亏。
代码
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
int main(){
unsigned long long N;
cin>>N;
stack<int> s, tmp;
vector<int> v;
int oriLen = 0, nowLen = 0;
while(N){
s.push(N%2);
N /= 2;
oriLen++;
}
int index = 0;
while(!s.empty()){
int cnt = 0;
while(s.top()){
s.pop();
cnt++;
if(s.empty()) break;
}
if(cnt > 2){
while(cnt){
tmp.push(cnt%2);
cnt /= 2;
}
while(!tmp.empty()){
v.push_back(tmp.top());
tmp.pop();
}
}
else{
for(int i = 0; i < cnt; i++)
v.push_back(1);
}
if(s.empty()) break;
while(!s.top()){
v.push_back(s.top());
s.pop();
if(s.empty()) break;
}
}
unsigned long long num = 0;
vector<int>::iterator it = v.begin();
for(; it != v.end(); it++){
num = num*2 + *it;
nowLen++;
}
cout<<num<<','<<oriLen<<','<<nowLen<<endl;
return 0;
}
1012. 素数进制A+B
https://acm.ecnu.edu.cn/contest/365/problem/1012/
题解
三个难点,读入/分割字符串后转整型,根据位数调整进制,大整数加法。
把这三个点都解决,剩下的就只是一些套路代码了。
先说读入,我是用两个vector<int>来存储A和B两个素数进制整数的,读入的时候先读A,按字符读入,碰到逗号停止,之前的数据按霍纳法则相加,存入vecA尾部。读到空格停止读A,开始读B。
这样就把两个数字按位从左至右存放在两个vector中了。
相加的时候,我建议把较短的vector加到较长的vector内部,因为短的加到长的里面,多出来的位数至多为1,只需要在最后使用至多一次insert语句,把carry位补上即可。如果是长的加到短的上,思考一下要多少个insert。
通过size成员函数确定长短。一个if-else解决。
素数进制,我建议开一个table,用下标映射位数,比如table[0]代表最低位,table[0]==2, table[1]==3……这样在处理进位的时候,开一个记录当前位数的变量digit,table[digit]的值即为进制数。
大整数的加法应该不难,从低到高模拟竖式加法,开一个carry变量作为进位,每次相加开一个tmp变量,同时加上carry和A,B位数上的数字,再进行处理即可。
最后判断是否carry为1,如果为1,在大数前插入一个1即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
int table[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
void ADD(vector<int> *A, vector<int> *B){
int length = A->size()-1;
int digits = 0;
int carry = 0;
for(int i = B->size()-1; i >= 0; i--){
int tmp = (*B)[i] + (*A)[length] + carry;
carry = 0;
if(tmp >= table[digits]){
tmp -= table[digits];
carry++;
}
(*A)[length] = tmp;
digits++;
length--;
}
for(int i = length; i >= 0; i--){
(*A)[i] += carry;
carry = 0;
if((*A)[i] >= table[digits]){
(*A)[i] -= table[digits];
carry++;
}
digits++;
}
if(carry) A->insert(A->begin(), 1);
}
int main(){
int T;
cin>>T;
getchar();
for(int i = 0; i < T; i++){
vector<int> A, B;
char ch;
int tmp = 0;
while((ch = getchar()) != ' '){
if(ch != ',')
tmp = tmp*10 + ch - 48;
else{
A.push_back(tmp);
tmp = 0;
}
}
A.push_back(tmp);
tmp = 0;
while((ch = getchar()) != '\n'){
if(ch != ',')
tmp = tmp*10 + ch - 48;
else{
B.push_back(tmp);
tmp = 0;
}
}
B.push_back(tmp);
cout<<"case #"<<i<<":"<<endl;
if(A.size()>=B.size()){
ADD(&A, &B);
vector<int>::iterator it = A.begin();
for(; it != A.end()-1; it++)
cout<<*it<<',';
cout<<*it<<endl;
}
else{
ADD(&B, &A);
vector<int>::iterator it = B.begin();
for(; it != B.end()-1; it++)
cout<<*it<<',';
cout<<*it<<endl;
}
}
return 0;
}
1013. 负基数进制转换
https://acm.ecnu.edu.cn/contest/365/problem/1013/
题解
难点只有一个,怎么把十进制转成负R进制。
我手写了好几种情况,找到一个规律。取模余的数必须为正数,否则没法排列。每次取余之后除以负数之前,要减去余数。
比如-11转-3进制,计算机算出来第一次余数为-2,但余数不能负,所以余数就是1,-11-1=-12,-12/-3=4;然后4模-3,明显是1,3/-3=-1;-1模-3,得2,-3/-3=1;1模3得1,0/3=0;因此转出来为1211。
掌握这个规则就很好写了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int mod(int a, int b){
for(int i = 0; i < abs(b); i++){
if(!((a-i) % b)) return i;
}
return 0;
}
int main(){
int N, R;
cin>>N>>R;
if(!N){
cout<<0<<endl;
return 0;
}
char table[20] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
stack<char> s;
while(N){
int num = mod(N, R);
s.push(table[abs(num)]);
N -= num;
N /= R;
}
while(!s.empty()){
cout<<s.top();
s.pop();
}
cout<<endl;
return 0;
}
1014. i-1 进制(Easy)
https://acm.ecnu.edu.cn/contest/365/problem/1014/
题解
上当了,原来是往回转。根本不需要考虑什么余数,直接按照霍纳法则一个个往下加就行了。
我定义了一个复数类,用于重载乘法和加法运算符,很方便。这样直接按照实数的规则转换即可。
这题还有一个比较坑的点是复数的书写,各种省略数字,符号的情况都要考虑到。
代码
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
class complex{
private:
long long re, im, remain;
public:
complex(long long r, long long i){
re = r;
im = i;
if(re%2 == im%2) remain = 0;
else remain = 1;
}
complex(const complex &a){
re = a.re;
im = a.im;
remain = a.remain;
}
complex operator*(const complex &a) const{
long long r, i;
r = re*a.re - im*a.im;
i = re*a.im + im*a.re;
return complex(r, i);
}
complex operator+(const complex &a) const{
long long r, i;
r = re+a.re;
i = im+a.im;
return complex(r, i);
}
complex operator+(const long long &a) const{
long long r, i;
r = re+a;
i = im;
return complex(r, i);
}
void myPrint(){
if(re!=0) cout<<re;
if(re!=0&&im>0) cout<<'+';
if(im<0) cout<<'-';
if(im!=1&&im!=0&&im!=-1) cout<<abs(im);
if(im!=0) cout<<'i'<<endl;
}
};
int main(){
complex a(-1, 1);
char str[70] = {'\0'};
int table[255] = {0};
for(int i = 48; i < 58; i++)
table[i] = i-48;
for(int i = 65; i < 71; i++)
table[i] = i-55;
cin>>str;
if(str[2]=='0'){
cout<<0<<endl;
return 0;
}
stack<int> s;
vector<int> v;
for(int i = 2; i < strlen(str); i++){
int num = table[str[i]];
while(num){
s.push(num%2);
num /= 2;
}
for(int j = 0; j < 4-s.size(); j++)
v.push_back(0);
while(!s.empty()){
v.push_back(s.top());
s.pop();
}
}
complex result(0, 0);
for(int i = 0; i < v.size(); i++)
result = result * a + v[i];
result.myPrint();
return 0;
}
1015. n! 进制
https://acm.ecnu.edu.cn/contest/365/problem/1015/
题解
又上当了,这题本质是个贪心法。每一位是上一位整除位权后得到的余数,再整除这一位的位权得到的。比如10,10/6 = 1...4,4/2 = 2...0,0/1 = 0。因此10->120。
先算出转换之后的位数,再一个个除下来就行了。
代码
#include <iostream>
#include <iterator>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
int fac(int n){
if(n==0||n==1) return 1;
else return n*fac(n-1);
}
int main(){
int T;
cin>>T;
int table[11] = {0};
for(int i = 0; i < 11; i++)
table[i] = fac(i);
for(int i = 0 ; i < T; i++){
cout<<"case #"<<i<<":"<<endl;
int n;
cin>>n;
if(n==0){cout<<0<<endl; continue;}
if(n==1){cout<<1<<endl; continue;}
vector<int> v;
int tmp = n;
int cnt = 0;
for(cnt = 10; cnt > 0; cnt--){
if(tmp > table[cnt]) break;
}
while(n){
v.push_back(n/table[cnt]);
n%=table[cnt--];
}
while(cnt--) v.push_back(0);
for(int j = 0; j < v.size(); j++)
cout<<v[j];
cout<<endl;
}
return 0;
}
1016. 平衡三进制
https://acm.ecnu.edu.cn/contest/365/problem/1016/
题解
映射是肯定的,将2映射成-1。具体映射方法不提了,看代码就懂了。
这题最难的点在于怎么输出,样例只给了3种情况的输出,其实还有别的隐藏情况,贼恶心。
首先,如果整数部分为0,省略整数,直接输出分数。但是分数不能直接输出,要保证分母恒为正数,这个需要在处理分数的过程中拎出来单独讨论。
然后,如果整数部分与小数部分异号,需要化为同号,对小数和整数同时进行调整。具体的调整还要再分情况。
再者,找gcd要用辗转相除,否则有一个点超时。
代码写得很乱,懒得改了。纯恶心人的题,服了。
代码
#include <iostream>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
long long gcd(long long a,long long b){
while(b^=a^=b^=a%=b);
return a;
}
class Fraction{
private:
int sig;
long long numerator;
long long denominator;
public:
Fraction(long long n, long long d){
numerator = n;
denominator = d;
if (n*d<0) {
sig = 0;
if(n>0){
n*=-1;
d*=-1;
}
}
if (n*d==0) sig = 2;
if (n*d>0){
sig = 1;
if(n<0){
n *= -1;
d *= -1;
}
}
}
Fraction operator/(const int& n) const{
return Fraction(numerator, denominator*n);
}
Fraction operator+(const int& n) const{
return Fraction(numerator+denominator*n, denominator);
}
void myPrint(){
if(numerator) cout<<numerator<<' '<<denominator<<endl;
}
int isPos(){
return sig;
}
Fraction simp(Fraction c){
long long g = gcd(c.numerator, c.denominator);
long long n = c.numerator/g;
long long d = c.denominator/g;
if (n*d<0){
sig = 0;
if(n>0){
n*=-1;
d*=-1;
}
}
if (n*d==0) sig = 2;
if (n*d>0){
sig = 1;
if(n<0){
n *= -1;
d *= -1;
}
}
return Fraction(n,d);
}
};
int main(){
char str[35] = {'\0'};
int table[255] = {0};
table['1'] = 1; table['2'] = -1;
cin>>str;
int iLen = 0, dLen = 0;
while(str[iLen]!='.' && str[iLen]!='\0')
iLen++;
if(strlen(str)==1 && str[0] == '0'){
cout<<0;
return 0;
}
long long iNum = 0;
for(int i = 0; i < iLen; i++)
iNum = iNum*3 + table[str[i]];
Fraction f(0, 1);
for(int i = strlen(str)-1; i >= iLen; i--)
f = f/3 + table[str[i]];
f = f.simp(f);
if(iNum > 0){
if(f.isPos()==1)
cout<<iNum<<' ';
else{
if(f.isPos()==0){
iNum--;
f = f + 1;
if(iNum) cout<<iNum;
cout<<' ';
}
}
}
else{
if(iNum != 0){
if(f.isPos()==0){
cout<<iNum<<' ';
f = f / (-1);
}
else{
if(f.isPos()==1){
iNum++;
f = f + (-1);
if(iNum) cout<<iNum;
cout<<' ';
f = f / (-1);
}
}
}
}
f = f.simp(f);
if(f.isPos() == 2) cout<<iNum;
else f.myPrint();
return 0;
}
1017. -1+i 进制
https://acm.ecnu.edu.cn/contest/365/problem/1017/
题解
先列出来要完成的功能:复数除法,复数求余;然后是读入复数的功能。
再看数据范围,10^18,肯定开long long了。
先定义一个复数类,成员变量为实部和虚部。重载两个运算符,完成除法和求余。注意这里的除法要整除,因此要先求余,然后减去余数,再除以被除数。
在转换进制的时候,需要一个函数判断复数是否为0,也写进类中。
读入的时候避开符号,讨论各种情况,可以拿纸列一下,情况比较多,全部都要考虑到。
代码
#include <iostream>
#include <cstring>
#include <stack>
#include <cmath>
using namespace std;
class Complex{
private:
long long real;
long long imag;
public:
Complex(long long r, long long i){
real = r;
imag = i;
}
Complex operator/(const Complex &c) const{
int flag = 1;
long long r = real;
long long i = imag;
if(abs(real)%2 == abs(imag)%2)
flag = 0;
if(flag){
r--;
}
return Complex((r*c.real+i*c.imag)/(c.real*c.real+c.imag*c.imag),
(i*c.real-r*c.imag)/(c.real*c.real+c.imag*c.imag));
}
int operator%(const Complex &c) const{
return (*this/c).getR();
}
int getR(){
if(abs(real)%2 == abs(imag)%2) return 0;
else return 1;
}
bool isZero(){
if(real == imag && real == 0) return true;
else return false;
}
};
int main(){
char str[100] = {'\0'};
cin>>str;
if(str[0]=='0' && str[1]=='\0'){
cout<<0<<endl;
return 0;
}
int start = 0;
int rSig = 1, iSig = 1;
if(str[0]=='-'){
start = 1;
rSig = -1;
}
long long tmp = 0, re = 0, im = 0;
while(str[start]!='+' && str[start]!='-' && str[start]!='\0' && str[start]!='i')
tmp = tmp*10 + str[start++] - 48;
if(str[start]=='i'){
if(!tmp) im = 1*rSig;
else im = tmp*rSig;
}
else{
re = tmp*rSig;
if(str[start]=='-')
iSig = -1;
start++;
tmp = 0;
while(str[start]!='\0' && str[start]!='i')
tmp = tmp*10 + str[start++] - 48;
if(str[start]=='i'){
if(!tmp) im = 1*iSig;
else im = tmp*iSig;
}
}
Complex c(re, im);
Complex t(-1, 1);
stack<int> s;
s.push(c.getR());
while(!c.isZero()){
s.push(c%t);
c = c/t;
}
s.pop();
while(!s.empty()){
cout<<s.top();
s.pop();
}
cout<<endl;
return 0;
}
1018. 平衡三进制 II
https://acm.ecnu.edu.cn/contest/365/problem/1018/
题解
这题照着题目给的提示一步步做下去就做完了。
我是建立了一个带分数类,自动分离整数部分和小数部分,自动判断分数是否可以约分,还重载了两个操作符。因此后面对于分数的处理都比较简单。
但比较复杂的是后面处理三进制转平衡三进制的步骤,需要加上不少特殊情况的判定,最好拿纸笔写一下有什么特殊情况。
不难,debug挺烦躁的。
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
class MixedNum{
public:
long long in, nu, de;
MixedNum(long long n, long long d){
in = n/d;
nu = n%d;
if(nu == 0) d = 0;
de = d;
}
MixedNum(long long i, long long n, long long d){
in = i;
nu = n;
if(nu == 0) d = 0;
de = d;
}
MixedNum operator-(const long long& a)const{
return MixedNum(in-a, nu, de);
}
MixedNum operator*(const long long& a)const{
if(!(de%a))
return MixedNum(in*de+nu, de/a);
return MixedNum((in*de+nu)*a, de);
}
};
int main(){
long long n, d;
cin>>n>>d;
MixedNum num(n, d);
stack<int> s;
vector<int> v;
vector<int> dec;
int alp[3] = {2, 0, 1};
int *table = alp+1;
long long integer = num.in;
while(integer){
s.push(integer%3);
integer/=3;
}
while(!s.empty()){
v.push_back(s.top());
s.pop();
}
num = num - num.in;
while(num.de){
num = num * 3;
dec.push_back(num.in);
num = num - num.in;
}
int carry = 0;
if(dec.size()){
for(int i = dec.size()-1; i >= 0; i--){
dec[i] = dec[i] + 1 + carry;
carry = 0;
if(dec[i] >= 3){
dec[i] -= 3;
carry++;
}
}
}
if(!v.size()) v.push_back(0);
for(int i = v.size()-1; i >= 0; i--){
v[i] = v[i] + 1 + carry;
carry = 0;
if(v[i] >= 3){
v[i] -= 3;
carry++;
}
}
int vLen = v.size();
if(carry) v.insert(v.begin(), carry);
int end = v.size() - vLen;
for(int i = dec.size()-1; i >= 0; i--)
dec[i]--;
for(int i = v.size()-1; i >= end; i--)
v[i]--;
if(dec.size()){
while(!dec[dec.size()-1]) {
dec.pop_back();
if(!dec.size()) break;
}
}
while(!v[0]){
v.erase(v.begin());
if(!v.size()) break;
}
if(!v.size()) cout<<0;
for(int i = 0; i < v.size(); i++)
cout<<table[v[i]];
if(dec.size()){
cout<<'.';
for(int i = 0; i < dec.size(); i++)
cout<<table[dec[i]];
}
cout<<endl;
return 0;
}
1019. 文件排序
https://acm.ecnu.edu.cn/contest/365/problem/1019/
题解
定义一个类。
class File{
public:
int ye, mo, da, ho, mi;//年月日时分
long long size;
string name;
}
然后定义匹配的输入输出格式,需要的成员函数即可。
cmp很好写,区分qsort和sort的格式。
代码
#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <string>
using namespace std;
class File{
public:
int ye, mo, da, ho, mi;
long long size;
string name;
File(){
ye = 0; mo = 0; da = 0; ho = 0; mi = 0;
size = 0;
name = "";
}
File(int year, int month, int day, int hour, int minute,
long long fSize, string fName){
ye = year; mo = month; da = day; ho = hour; mi = minute;
size = fSize;
name.swap(fName);
}
friend istream &operator>>(istream &in, File &f){
in>>f.ye;
getchar();
in>>f.mo;
getchar();
in>>f.da>>f.ho;
getchar();
in>>f.mi;
scanf("%lld", &f.size);
in>>f.name;
return in;
}
friend ostream &operator<<(ostream &out, File &f){
out<<f.ye<<'-';
if(f.mo<10) out<<0;
out<<f.mo<<'-';
if(f.da<10) out<<0;
out<<f.da<<' ';
if(f.ho<10) out<<0;
out<<f.ho<<':';
if(f.mi<10) out<<0;
out<<f.mi<<' ';
printf("%16lld ", f.size);
out<<f.name;
out<<endl;
return out;
}
};
bool cmp_SIZE(File a, File b){
if(a.size != b.size)
return a.size < b.size;
else return a.name < b.name;
}
bool cmp_NAME(File a, File b){
return a.name < b.name;
}
bool cmp_TIME(File a, File b){
if(a.ye != b.ye) return a.ye < b.ye;
else{
if(a.mo != b.mo) return a.mo < b.mo;
else{
if(a.da != b.da) return a.da < b.da;
else{
if(a.ho != b.ho) return a.ho < b.ho;
else{
if(a.mi != b.mi) return a.mi < b.mi;
}
}
}
}
return a.name < b.name;
}
int main(){
int n = 1;
while(n){
cin>>n;
if(n==0) break;
File *files = new File[n];
for(int i = 0; i < n; i++)
cin>>files[i];
string cmd1, cmd2;
cin>>cmd1;
cin>>cmd2;
if(cmd2.find("NAME")!=string::npos) sort(files, files + n, cmp_NAME);
if(cmd2.find("SIZE")!=string::npos) sort(files, files + n, cmp_SIZE);
if(cmd2.find("TIME")!=string::npos) sort(files, files + n, cmp_TIME);
for(int i = 0; i < n; i++)
cout<<files[i];
cout<<endl;
}
return 0;
}
1020. 字串排序
https://acm.ecnu.edu.cn/contest/365/problem/1020/
题解
卡题的点:要用strcmp就别用sort,用qsort,两个函数cmp的返回值不一样。
其他没啥难度,抽象一个结构体,里面有字符串和包含的数字。之后开结构体数组排序输出即可。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct str{
char s[35];
long long num;
}S;
int cmp(const void *A, const void *B){
S Q = *(S*)A;
S P = *(S*)B;
if(Q.num == P.num) return strcmp(Q.s, P.s);
else return Q.num - P.num;
}
int main(){
S strs[105];
for(int i = 0; i < 105; i++)
strs[i].num = -1;
int k = 0;
while(scanf("%s", strs[k].s)!=EOF){
int slen = strlen(strs[k].s);
long long n = 0, flag = 0;
for(int i = 0; i < slen; i++){
if(strs[k].s[i]<='9' && strs[k].s[i]>='0'){
n = n*10 + strs[k].s[i] - 48;
flag = 1;
}
}
if(flag)
strs[k++].num = n;
else
strs[k++].num = -1;
}
qsort(strs, k, sizeof(S), cmp);
for(int i = 0; i < k; i++)
printf("%s ", strs[i].s);
return 0;
}
1021. 随机排序
https://acm.ecnu.edu.cn/contest/365/problem/1021/
题解
开字母表,题目中没有明确给出大小写相同情况下,谁比较大。根据样例,小写字母应该比相同的大写字母大,举个例子(a>A, a<B)。手写一个比较函数,逐个字符比较过去,得出两个字符串比较的布尔值。最后输出即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int table[130] = {0};
typedef struct strs{
char s[25];
}S;
bool cmp(S s1, S s2){
int len1 = strlen(s1.s);
int len2 = strlen(s2.s);
int minLen = min(len1, len2);
for(int i = 0; i < minLen; i++){
if(s1.s[i]!=s2.s[i]) return table[s1.s[i]] < table[s2.s[i]];
}
return len1 < len2;
}
int main(){
char ch;
int cnt = 0;
while(cin>>ch){
for(int i = 0; i < 52; i+=2){
table[ch] = i;
table[ch+32] = i+1;
cin>>ch;
}
S strs[110];
int strN = 0;
int j = 0;
while(ch!='\n'){
strs[strN].s[j++] = ch;
ch = getchar();
if(ch==' '){
strs[strN].s[j++] = '\0';
strN++;
j = 0;
ch = getchar();
}
}
strs[strN].s[j++] = '\0';
sort(strs, strs+strN+1, cmp);
for(int i = 0; i < strN+1; i++){
if(i!=strN) cout<<strs[i].s<<' ';
else cout<<strs[i].s<<endl;
}
}
return 0;
}
1022. 邮件地址排序
https://acm.ecnu.edu.cn/contest/365/problem/1022/
题解
已知字符总量,不知道有多少组。因此使用结构体存储指针,指针指向字符串起始地址的数据结构。定义一个大数组,存储所有的字符。手动嵌入'\0'进行分割。再将结构体数组中的元素包含的指针指向指定的字符串起始地址即可。
cmp函数,由于cmp的返回值类型是bool,所以需要对返回-1,0,1的strcmp函数进行讨论。当strcmp返回0的时候,尽量使cmp函数返回false,减少交换次数。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct Email{
char *user;
char *domain;
}E;
void myPrint(E e){
cout<<e.user<<'@'<<e.domain<<endl;
}
bool cmp(E a, E b){
int flag1 = strcmp(a.domain, b.domain);
if(!flag1){
int flag2 = strcmp(a.user, b.user);
if(flag2 <= 0) return false;
else return true;
}
if(flag1 > 0) return false;
else return true;
}
int main(){
int cnt = 0;
int n;
cin>>n;
getchar();
char tmp[1] = {'\0'};
E* es = (E*)malloc(sizeof(E)*(n+1));
char *str = (char*)malloc(sizeof(char)*2000001);
for(int i = 0; i < n; i++){
es[i+1].user = tmp;
es[i+1].domain = tmp;
char ch;
es[i].user = str+cnt;
while((ch=getchar())!='@')
str[cnt++] = ch;
str[cnt++] = '\0';
es[i].domain = str+cnt;
while((ch=getchar())!='\n')
str[cnt++] = ch;
str[cnt++] = '\0';
}
sort(es, es+n, cmp);
for(int i = 0; i < n; i++)
myPrint(es[i]);
free(es);
free(str);
return 0;
}
1023. 发愁
https://acm.ecnu.edu.cn/contest/365/problem/1023/
题解
定义结构体进行排序。从排序条件中得知,一个结构体应该包含4个成员:积分,胜场,负场,编号。然后根据读入的数字构建结构体数组。
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Team{
int num;
int wins;
int lose;
int score;
}T;
//初始化结构体模板
T* newTeams(int n){
T* t = (T*)malloc(sizeof(T)*(n+5));
for(int i = 1; i <= n+1; i++){
t[i].num = i;
t[i].wins = 0;
t[i].lose = 0;
t[i].score = 0;
}
return t;
}
bool cmp(T a, T b){
if(a.score != b.score) return a.score > b.score;
else{
if(a.wins != b.wins) return a.wins > b.wins;
else{
if(a.lose != b.lose) return a.lose < b.lose;
else return a.num < b.num;
}
}
}
int main(){
int n, m;
cin>>n>>m;
while(n!=0||m!=0){
T* t = newTeams(n);
for(int i = 0; i < m; i++){
int a,b,c;
cin>>a>>b>>c;
if(c>0) {t[a].wins++; t[b].lose++; t[a].score+=3; t[b].score--;}
else{
if(c==0) {t[a].score++;t[b].score++;}
else {t[b].wins++; t[a].lose++; t[b].score+=3; t[a].score--;}
}
}
sort(t+1, t+n+1, cmp);
for(int i = 1; i <= n; i++)
cout<<t[i].num<<' ';
cout<<endl;
cin>>n>>m;
}
return 0;
}
1024. 成绩排序
https://acm.ecnu.edu.cn/contest/365/problem/1024/
题解
类似的题目上面讲过了,难度几乎没有。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct Stu{
char num[12];
int score;
}S;
bool cmp(S a, S b){
if(a.score != b.score) return a.score > b.score;
else return strcmp(a.num, b.num)>=0 ? false:true;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N, M, G;
cin>>N>>M>>G;
int *table = (int*)malloc(sizeof(int)*(M+1));
for(int j = 1; j <= M; j++)
cin>>table[j];
S *stu = (S*)malloc(sizeof(S)*(N+1));
int cnt = 0;
for(int j = 0; j < N; j++)
stu[j].score = 0;
for(int j = 0; j < N; j++){
cin>>stu[j].num;
int s;
cin>>s;
for(int k = 0; k < s; k++){
int l;
cin>>l;
stu[j].score += table[l];
}
if(stu[j].score>=G) cnt++;
}
sort(stu, stu+N, cmp);
cout<<"case #"<<i<<':'<<endl;
cout<<cnt<<endl;
for(int j = 0; j < N; j++){
if(stu[j].score>=G) cout<<stu[j].num<<' '<<stu[j].score<<endl;
}
}
return 0;
}
1025. 字串非重复字符数排序
https://acm.ecnu.edu.cn/contest/365/problem/1025/
题解
字符映射的思想。开字母表记录已经出现过的字符。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct Str{
char s[25];
int num;
}S;
S* newS(int n){
S* s = (S*)malloc(sizeof(S)*(n+5));
for(int i = 0; i < n+5; i++)
s[i].num = 0;
return s;
}
bool cmp(S *a, S *b){
if(a->num!=b->num) return a->num > b->num;
else return strcmp(a->s, b->s)<=0? true:false;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int n;
cin>>n;
getchar();
S* s = newS(n);
S* sp[105];
for(int j = 0; j < n; j++){
char ch;
int cnt = 0;
int tb[256] = {0};
while((ch=getchar()) != '\n'){
s[j].s[cnt++] = ch;
if(!tb[ch]){
s[j].num++;
tb[ch]++;
}
}
s[j].s[cnt++] = '\0';
sp[j] = s+j;
}
sort(sp, sp+n, cmp);
cout<<"case #"<<i<<':'<<endl;
for(int j = 0; j < n; j++)
cout<<sp[j]->s<<endl;
}
return 0;
}
1026. 点对
https://acm.ecnu.edu.cn/contest/365/problem/1026/
题解
真·签到题
代码
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int a[100001] = {0};
for(int i = 0; i < n; i++)
cin>>a[i];
sort(a, a+n);
int sum = 0;
for(int i = 0; i < n; i+=2)
sum+=a[i+1]-a[i];
cout<<sum<<endl;
return 0;
}
1027. 极坐标排序
https://acm.ecnu.edu.cn/contest/365/problem/1027/
题解
定义结构体数组排序的模板题。注意分类讨论不同象限的角度。
代码
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct Polar{
double len;
double ang;
}P;
void convert(P *p, double x, double y){
p->len = pow(x*x + y*y, 0.5);
p->ang = atan(y/x);
if(p->ang <= 0) {
if(y<0)
p->ang = (2*M_PI + p->ang);
else
if(x<0)
p->ang = (M_PI + p->ang);
}
else{
if(x<0 || y <0)
p->ang = (M_PI + p->ang);
}
}
bool cmp(P a, P b){
if(a.ang!=b.ang) return a.ang<b.ang;
else return a.len>b.len;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N;
cin>>N;
P *p = (P*)malloc(sizeof(P)*(N+1));
for(int j = 0; j < N; j++){
double x, y;
cin>>x>>y;
convert(p+j, x, y);
}
sort(p, p+N, cmp);
printf("case #%d:\n", i);
for(int j = 0; j < N; j++)
printf("(%.4f,%.4f)\n", p[j].len, p[j].ang);
}
return 0;
}
1028. 排序去重
https://acm.ecnu.edu.cn/contest/365/problem/1028/
题解
桶排序 秒了,不懂的可以搜一下什么是基数排序
代码
#include <stdio.h>
#include <stdlib.h>
int main()
{
char sort;
int nums[1001];
int i = 0;
for(i = 0; i <= 1000 ; ++i)
nums[i] = 0;
while((scanf("%c", &sort)) != EOF){
while((scanf("%d" , &i)) != EOF){
nums[i]++;
}
}
if(sort == 'A'){
for(i = 0; i <= 1000 ; ++i)
if(nums[i] > 0)
printf("%d ", i);
}
else{
for(i = 1000; i > 0 ; --i)
if(nums[i] > 0)
printf("%d ", i);
}
printf("\n");
}
1029. 字符排序
https://acm.ecnu.edu.cn/contest/365/problem/1029/
题解
这题太适合用基数排序了。先开一个长char数组存储整行字符,开一个长度大于255的int数组存储字符个数。读入使用ch=getchar(),读入字符的同时,令字母表数组的第ch位+1。比如读到A,先存入字符串尾部,再令table['A']++。
然后无需任何操作,直接进入输出阶段。
扫描char数组,如果碰到字母,那么扫描table['A']~table['Z'],如果有元素不为0,输出下标对应的字符,元素-1,跳出内层扫描。如果碰到非字母,直接输出即可。
代码
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
int main(){
int T;
cin>>T;
getchar();
for(int i = 0; i < T; i++){
char *str = (char*)malloc(sizeof(char)*205);
int tb[260] = {0};//字母表
char ch;
int cnt = 0;
while((ch=getchar())!='\n'){
tb[ch]++;
str[cnt++] = ch;
}
//这步做完后,比如字符串是CCAA,那么tb['C']==2,tb['A']==2
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < cnt; j++){
if(isalpha(str[j])){
for(char k = 'A'; k <= 'Z'; k++){
if(tb[k]){
cout<<k;
tb[k]--;
break;
}
}
}
else{
cout<<str[j];
}
}
cout<<endl;
free(str);
}
return 0;
}
1030. 按整数最高位的值排序
https://acm.ecnu.edu.cn/contest/365/problem/1030/
题解
取最高位方法,小于10取绝对值。大于等于10取绝对值整除10,直到小于10为止。
代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct LInt{
long long num;
int fnum;
}L;
bool cmp(L a, L b){
if(a.fnum != b.fnum) return a.fnum > b.fnum;
else return a.num < b.num;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N;
cin>>N;
L* l = (L*)malloc(sizeof(L)*(N+1));
for(int j = 0; j < N; j++){
long long tmp;
cin>>tmp;
l[j].num = tmp;
if(abs(tmp)<10) l[j].fnum = abs(tmp);
else{
while(abs(tmp)>=10) tmp/=10;
l[j].fnum = abs(tmp);
}
}
sort(l, l+N, cmp);
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < N; j++)
cout<<l[j].num<<' ';
cout<<endl;
free(l);
}
return 0;
}
1031. 最小向量点积
https://acm.ecnu.edu.cn/contest/365/problem/1031/
题解
两个数组对应两个向量,一个升序排列,一个降序排列,然后相乘即可。数学证明有空的可以证一下。
代码
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp1(int a, int b){
return a<b;
}
bool cmp2(int a, int b){
return a>b;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int n;
cin>>n;
int *a = (int*)malloc(sizeof(int)*(n+1));
int *b = (int*)malloc(sizeof(int)*(n+1));
for(int j = 0; j < n; j++)
cin>>a[j];
for(int j = 0; j < n; j++)
cin>>b[j];
sort(a, a+n, cmp1);
sort(b, b+n, cmp2);
long long sum = 0;
for(int j = 0; j < n; j++)
sum += a[j]*b[j];
cout<<"case #"<<i<<":"<<endl;
cout<<sum<<endl;
free(a);
free(b);
}
return 0;
}
1032. 行数据的排序
https://acm.ecnu.edu.cn/contest/365/problem/1032/
题解
最长50个数,把数字读进去后,剩余全填-1,就可以避免比较长短。耗时会略长。
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Set{
int a[51];
}S;
bool cmp(S x, S y){
for(int i = 0; i < 51; i++){
if(x.a[i]!=y.a[i]) return x.a[i] > y.a[i];
}
return false;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N;
cin>>N;
S *s = (S*)malloc(sizeof(S)*(N+1));
for(int j = 0; j < N+1; j++){
for(int k = 0; k < 51; k++)
s[j].a[k]=-1;
}
for(int j = 0; j < N; j++){
int tmp;
cin>>tmp;
int k = 0;
while(tmp != -1){
s[j].a[k++] = tmp;
cin>>tmp;
}
}
sort(s, s+N, cmp);
for(int j = 0; j < N; j++){
int k = 0;
while(s[j].a[k]!=-1)
cout<<s[j].a[k++]<<' ';
cout<<endl;
}
}
return 0;
}
1033. Maya历日期的排序
https://acm.ecnu.edu.cn/contest/365/problem/1033/
题解
建立字符串和整型的映射。然后开结构体数组写cmp排序即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef struct Date{
int year;
int month;
int day;
}D;
char tb[20][10]={"pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol",
"chen", "yax", "zac", "ceh", "mac", "kankin", "muan", "pax",
"koyab", "cumhu", "uayet"};
bool cmp(D a, D b){
if(a.year != b.year) return a.year < b.year;
else{
if(a.month != b.month) return a.month < b.month;
else return a.day < b.day;
}
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N;
cin>>N;
D *d = (D*)malloc(sizeof(D)*(N+1));
int day;
char month[10] = {'\0'};
int year;
for(int j = 0; j < N; j++){
cin>>d[j].day;
getchar();
cin>>month;
cin>>d[j].year;
for(int k = 0; k < 19; k++){
if(!strcmp(month, tb[k])){
d[j].month = k+1;
break;
}
}
}
sort(d, d+N, cmp);
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < N; j++)
cout<<d[j].day<<". "<<tb[d[j].month-1]<<' '<<d[j].year<<endl;
free(d);
}
return 0;
}
1034. 字符频率
https://acm.ecnu.edu.cn/contest/365/problem/1034/
题解
cmp里面三个分支,还是区分sort和qsort的区别,这里提供一种使用sort的写法。
别的都是很标准的读入输出,没啥花里胡哨的。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct character{
char c;
double alp;
}C;
bool cmp(C a, C b){
if(abs(a.alp - b.alp) > 0.001) return a.alp > b.alp;
if(abs(a.c-b.c) == 32) return a.c > b.c;
return a.c < b.c;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
double alp[26];
for(int j = 0; j < 26; j++)
cin>>alp[j];
char ch;
C str[105];
int len = 0;
getchar();
while((ch=getchar())!='\n'){
str[len].c = ch;
if(ch <= 'z' && ch >= 'a')
str[len++].alp = alp[ch-97];
else
str[len++].alp = alp[ch-65];
}
sort(str, str+len, cmp);
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < len; j++)
cout<<str[j].c;
cout<<endl;
}
return 0;
}
1035. 表面积
https://acm.ecnu.edu.cn/contest/365/problem/1035/
题解
终于来道能卡住我的排序题了。这题数据总量很小,所以根本不用考虑什么情况下总面积最大。也就是完全无需数学推导,直接一个个枚举过去即可。当然不是让你把所有情况枚举,那要枚举n!的量级次,肯定超时。因此我们先写出总面积公式S = r_1^2 + r_1 h_1 + r_2 h2 + ... + r_m h_m
。只要令其中每一项均为最大,那么表面积就是最大的。
而这些圆盘中,有一个圆盘是要作为底部圆盘的,其他的圆盘只要考虑侧面积。因此我们随意假定一个圆盘是底部圆盘(无视圆形面积大小排序),对剩下的所有圆盘按照侧面积排序,选侧面积最大的几个圆盘即可。
这样就相当于枚举了所有可能的情况。
代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct Circle{
unsigned long long cir;
unsigned long long side;
unsigned long long all;
}C;
bool cmp(C a, C b){
return a.side > b.side;
}
int main(){
int n, m;
cin>>n>>m;
vector<C> v1;
for(int i = 0; i < n; i++){
unsigned long long r, h;
cin>>r>>h;
C tmp;
tmp.cir = r*r;
tmp.side = 2*r*h;
tmp.all = r*r + 2*r*h;
v1.push_back(tmp);
}
sort(v1.begin(), v1.end(), cmp);
vector<unsigned long long> result;
for(int i = 0; i < n; i++){
unsigned long long s = 0;
vector<C> tmp;
for(int j = 0; j < n; j++)
tmp.push_back(v1[j]);
s += tmp[i].all;
tmp.erase(tmp.begin()+i);
for(int j = 0; j < m-1; j++)
s += tmp[j].side;
result.push_back(s);
}
unsigned long long ans = 0;
for(int i = 0; i < n; i++){
if(ans < result[i])
ans = result[i];
}
cout<<ans<<endl;
return 0;
}
1036. 计算总步数
https://acm.ecnu.edu.cn/contest/365/problem/1036/
题解
这题本质上是一个数学题。因为第一步要走1格,所以先算出两点的x坐标差值和y坐标差值,记为dx, dy。这样就相当于从(0,0)移动到(dx, dy)。
步数为1,2,4,...,所以只有第一步会改变某一个坐标的奇偶性。因此,只有在dx,dy其中有且仅有一个奇数的时候才可能有解。
假设第一次走过了,我们会得到两个偶数的dx,dy。这时候需要走第二步,要走2格。不妨将dx,dy全部除以2,这样就回到了第一种情况。
这样就形成了一个循环。
设置边界条件之后,就做出来了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef struct Point{
long long x, y;
unsigned long long md;
}P;
bool cmp(P a, P b){
if(a.md != b.md) return a.md > b.md;
else{
if(a.x != b.x) return a.x < b.x;
else{
return a.y < b.y;
}
}
}
long long f(int n){
long long sum = 1;
for(int i = 0; i < n; i++)
sum*=2;
return sum;
}
int main(){
int n;
cin>>n;
P p[104];
for(int i = 0; i < n; i++){
cin>>p[i].x>>p[i].y;
p[i].md = abs(p[i].x) + abs(p[i].y);
}
sort(p, p+n, cmp);
unsigned long long d1 = abs(p[0].x-p[1].x);
unsigned long long d2 = abs(p[0].y-p[1].y);
if(d1+d2 == 0 && d1 > 0) cout<<"18446744073709551616"<<endl;
else cout<<d1+d2<<endl;
int ans = 0;
for(int i = 0; i < n-1; i++){
long long x = p[i].x;
long long y = p[i].y;
unsigned long long dx, dy;
dx = abs(p[i+1].x - x);
dy = abs(p[i+1].y - y);
while(1){
if(dx == 0 && dy == 0) break;
if(dx+dy == 1){
ans++;
break;
}
if(dx%2 == dy%2){
cout<<ans<<endl;
return 0;
}
ans++;
if(dx%2) dx^=dy^=dx^=dy;
dx/=2;
unsigned long long t1 = (dy-1)/2;
unsigned long long t2 = (dy+1)/2;
if(dx%2 == t1%2) dy = t2;
else dy = t1;
}
}
cout<<ans<<endl;
return 0;
}
1037. 挑数字
https://acm.ecnu.edu.cn/contest/365/problem/1037/
题解
排序 挑相邻的数字即可
计算新sum的时候用公式,不要累加 会超时
代码
#include <bits/stdc++.h>
using namespace std;
bool cmp(unsigned long long a, unsigned long long b){
return a>b;
}
int main(){
int n, m;
cin>>n>>m;
vector<unsigned long long> v;
for(int i = 0; i < n; i++){
unsigned long long tmp;
cin>>tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end(), cmp);
int i = 0, j = m - 1;
unsigned long long max = v[i];
unsigned long long sum = (m-1)*max;
unsigned long long tpSum = 0;
unsigned long long tpSum2 = 0;
for(int k = i+1; k <= j; k++)
sum -= v[k];
for(int k = m; k < n; k++){
tpSum += v[i+1];
i++;
tpSum2 += v[k];
unsigned long long tmp = sum + (v[k-m+1]-max) * (m-1) + tpSum - tpSum2;
if(tmp < sum){
i = k-m+1;
tpSum2 = 0;
tpSum = 0;
max = v[i];
sum = tmp;
}
}
cout<<sum<<endl;
return 0;
}
1038. 围栏
https://acm.ecnu.edu.cn/contest/365/problem/1038/
题解
我花了1分钟做完了,我觉得应该不用写题解。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
char ch = getchar();
int len = 1;
int maxLen = 1;
char tmp = ch;
while((ch = getchar())!=EOF){
if(maxLen < len)
maxLen = len;
if(ch == tmp)
len = 1;
else len++;
tmp = ch;
}
cout<<maxLen<<endl;
return 0;
}
1039. 字符组合
https://acm.ecnu.edu.cn/contest/365/problem/1039/
题解
一眼扫过去,不得了。组合不用想了,肯定dfs(深度优先搜索)。比如abc三个字母,每个字母有两种可能,选或者不选。通过递归把选和不选的情况做一个分叉,就形成了一棵二叉树,所有叶子节点就是要的答案。
去重就用基数排序的思想,或者开一个字母表,一个对照表,对照表的下标对应字母的ASCII码。读到字母,去对照表查找,如果为true则跳过,为false,改成true,把字母加进字母表。
然后就是格式问题了,这个应该不难处理。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef struct str{
char s[20];
}str;
void dfs(vector<vector<char>> *s, vector<char> alphabet, vector<char> tmp, int start, int end){
if(start > end) s->push_back(tmp);
else{
dfs(s, alphabet, tmp, start+1, end);
tmp.push_back(alphabet[start]);
dfs(s, alphabet, tmp, start+1, end);
}
}
int cmp(const void *A, const void *B){
return strcmp((*(str*)A).s, (*(str*)B).s);
}
int main(){
int T;
cin>>T;
getchar();
for(int k = 0; k < T; k++){
char ch;
bool table[256] = {false};
vector<char> alphabet;
vector<char> tmp;
vector<vector<char>> s;
while((ch = getchar())!='\n'){
if(!table[ch]){
table[ch] = true;
alphabet.push_back(ch);
}
}
sort(alphabet.begin(), alphabet.end());
dfs(&s, alphabet, tmp, 0, alphabet.size()-1);
cout<<"case #"<<k<<":"<<endl;
str *result = (str*)malloc(sizeof(str)*100000);
for(int i = 0; i < 100000; i++){
for(int j = 0; j < 20; j++)
result[i].s[j] = '\0';
}
int cnt = 0;
for(int i = 0; i < s.size(); i++){
if(s[i].size()){
for(int j = 0; j < s[i].size(); j++)
result[cnt].s[j] = s[i][j];
cnt++;
}
}
qsort(result, cnt, sizeof(str), cmp);
for(int i = 0; i < cnt; i++)
printf("%s\n", result[i].s);
free(result);
}
return 0;
}
1040. 字符串消除
https://acm.ecnu.edu.cn/contest/365/problem/1040/
题解
我是笨比,我只会四重循环硬算,一个个情况枚举过去。
听说有数学方法更快,反正数据规模就10^4,随便做了。
开个string类型插入更方便,vector也行吧。开数组还是太麻烦了。
代码
#include <bits/stdc++.h>
using namespace std;
string tb[3] = {"A", "B", "C"};
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
string s;
cin>>s;
int num = 0;
for(int j = 0; j <= s.size(); j++){
for(int k = 0; k < 3; k++){
string tmp = s;
tmp.insert(j, tb[k]);
int len = tmp.size();
while(1){
int flag = 0;
for (string::iterator it = tmp.begin(), t, s; it < tmp.end() - 1;){
if (*(it + 1) == *it){
flag = 1;
int x = it - tmp.begin();
t = it;
while (it < tmp.end() - 1 && *(it + 1) == *it)
it++;
tmp.erase(t, it + 1);
x = x < 0 ? 0 : x;
it = tmp.begin() + x;
}
else
it++;
}
if (flag == 0)
break;
}
num = num>(len-tmp.size())?num:len-tmp.size();
}
}
cout<<"case #"<<i<<":"<<endl;
cout<<num<<endl;
}
return 0;
}
1041. 十六进制
https://acm.ecnu.edu.cn/contest/365/problem/1041/
题解
一年前做的题,硬分类能很快做出来。
代码
#include <stdio.h>
int main()
{
char str[100000] = {'\0'};
char digit[100000] = {'\0'};
char *ps = str;
int j = 0;
int temp = 0;
gets(str);
while (*ps != '\0')
{
if (*ps == '0' && *(ps + 1) == 'x')
{
ps = ps + 2;
int i = 0;
while (*ps >= '0' && *ps <= '9' || *ps >= 'A' && *ps <= 'F' || *ps >= 'a' && *ps <= 'f')
{
digit[j] = *ps;
ps++;
j++;
i++;
}
if (i != 0)
{
j -= i;
unsigned int num = 0;
while (digit[j] != '\0')
{
if (digit[j] >= '0' && digit[j] <= '9')
num = num * 16 + digit[j] - '0';
else if (digit[j] >= 'A' && digit[j] <= 'F')
num = num * 16 + digit[j] - 'A' + 10;
else if (digit[j] >= 'a' && digit[j] <= 'f')
num = num * 16 + digit[j] - 'a' + 10;
j++;
}
temp++;
printf("%u ", num);
}
}
ps++;
}
if (temp == 0)
printf("-1");
return 0;
}
1042. 字串变换
https://acm.ecnu.edu.cn/contest/365/problem/1042/
题解
根据题意,可以很容易判断出何时输出-1。
首先得知,每个字符串都有一个基字符串,基字符串内没有连续且重复的字母。举个例子,aabbbc->abc, mmdjs->mdjs, ooooobo->obo。
如果输入进来的字符串的基字符串不严格相等,那么就不可能通过变换互相转换。输出-1。
因此,在读入字符串的时候,我们可以一边记录字符串中每个字母出现的次数,一边记录字符串的基,通过比较两个字符串的基,筛去所有输出-1的情况。
然后就是考虑如何变换字符串了。一眼看到时限10秒,只要运算语句次数控制在10^9内都可以接受。
观察到题目的数据范围,最坏情况是26个不同字符,找100个数,循环10^5次,三重循环三个数相乘,数量级不到10^9,我直接进行一个暴力的搜。
对基字符串中的每个字符分开处理,将总和相加就是答案。
对于每个字符,每个字符串有对应的权重a1,a2,...,an。寻找1-100中一个正整数t,使得sum(abs(ai-t))最小。如果你有空,可以试试看把范围缩小到min{an}-max{an},不知道对不对。
然后就是考虑数据结构了,我这里用了vector存放每个字符的出现次数。v.size()就是基字符串长度,很方便。在对这个vector开一个数组,可以是结构体数组,也可以是再套一个vector。没啥区别。
暴力搜索1.9s过了。这个算法还能优化,应该是缩小1-100的范围,在调试的时候出现了很多多余的计算,但我不会优化了,希望有大佬能解答。
代码
#include <bits/stdc++.h>
using namespace std;
typedef struct Data{
vector<int> v;
}D;
D d[100001];
int main(){
int n;
cin>>n;
getchar();
char ch;
char base[101] = {'\0'};
for(int i = 0; i < n; i++){
char tmp[101] = {'\0'};
int cnt = 0;
while((ch=getchar())!='\n'){
if(ch!=tmp[cnt-1]){
tmp[cnt] = ch;
cnt++;
d[i].v.push_back(1);
}
else
d[i].v[d[i].v.size()-1]++;
}
if(!i) strcpy(base, tmp);
else{
if(strcmp(base, tmp)){
cout<<-1<<endl;
return 0;
}
}
}
long long ans = 0;
for(int i = 0; i < d[0].v.size(); i++){
long long tmp;
for(int j = 1; j < 100; j++){
long long res = 0;
for(int k = 0; k < n; k++)
res += abs(d[k].v[i]-j);
if(j==1) tmp = res;
else tmp = min(tmp, res);
}
ans += tmp;
}
cout<<ans<<endl;
return 0;
}
1043. 统计单词个数
https://acm.ecnu.edu.cn/contest/365/problem/1043/
题解
这题比较坑的是单词的大小写问题,各种组合可以通过dfs逐个塞入vector再查重。因为单词一共就6个,也可以直接手动打表。我懒得想dfs怎么写了,所以这题通过打表变成签到题了。
代码
#include <bits/stdc++.h>
using namespace std;
string tb[35] = {"THE", "THe", "The", "ThE", "tHE", "tHe", "the", "thE",
"A", "a",
"AN", "An", "aN", "an",
"OF", "Of", "oF", "of",
"FOR", "FOr", "For", "FoR", "fOR", "fOr", "for", "foR",
"AND", "ANd", "And", "AnD", "aND", "aNd", "and", "anD"};
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int cnt = 0;
string s;
while(cin>>s){
int flag = 0;
for(int j = 0; j < 35; j++){
if(s == tb[j]){
flag = 1;
break;
}
}
if(!flag) cnt++;
if(cin.get()=='\n')
break;
}
cout<<"case #"<<i<<":"<<endl<<cnt<<endl;
}
return 0;
}
1044. 数据压缩
https://acm.ecnu.edu.cn/contest/365/problem/1044/
题解
签到题,不会重开
代码
#include <bits/stdc++.h>
using namespace std;
typedef struct Alpha{
char ch;
int n;
}A;
int main(){
int T;
cin>>T;
getchar();
for(int i = 0; i < T; i++){
char ch;
A tmp;
tmp.n = 0;
vector<A> v;
int alpha[255] = {0};
while((ch=getchar())!='\n'){
if(ch!=tmp.ch){
if(tmp.n)
v.push_back(tmp);
alpha[ch] = 1;
tmp.ch = ch;
tmp.n = 1;
}
else{
if(tmp.n == 255){
v.push_back(tmp);
tmp.n = 1;
}
else
tmp.n++;
}
}
v.push_back(tmp);
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < v.size(); j++)
cout<<v[j].n<<v[j].ch;
cout<<endl;
}
return 0;
}
1045. 一元多项式乘法
https://acm.ecnu.edu.cn/contest/365/problem/1045/
题解
不难,好烦。看代码注释就行了(一年前做的题
代码
#include <stdio.h>
#include <string.h>
int main(void)
{
char s1[120], s2[120];
while((scanf("%s %s",s1,s2))!=EOF)
{
int time[101]={0}, n1[51]={0}, n2[51]={0}, i, coe, exp, pro, sig;//coe:系数,exp:次数,pro:进程,sig:符号
int m=strlen(s1), n=strlen(s2);
//读第一个多项式
for(i=0, coe=0, exp=1, pro=0, sig=1; i<m; i++)
{
if(s1[i]=='x'&&pro!=0) {n1[0]=0; n1[1]=coe; pro=1;}//进程1,计算x的次数
else if(s1[i]=='x'&&pro==0)
{
if(s1[i+1]=='^') {coe=1*sig; pro=1;}
else {coe=1*sig; n1[1]=coe; pro=1;}
}
else if(s1[i]=='^') continue;
else if(pro!=1&&s1[i]=='+') {sig=1;}//加法
else if(pro==1&&s1[i]=='+') {pro=0;sig=1;}
else if(pro!=1&&s1[i]=='-') {sig=-1;}//减法
else if(pro==1&&s1[i]=='-') {pro=0;sig=-1;}
else if(pro==1)
{
exp=0;
while(s1[i]>='0'&&s1[i]<='9')
{
exp+=s1[i]-'0';
if(s1[i+1]>='0'&&s1[i+1]<='9'){exp*=10;i++;}
else break;
}
n1[exp]=coe;
n1[1]=0;
n1[0]=0;
}
else if(pro==0)//进程0,计算x的系数
{
coe=0;
while(s1[i]>='0'&&s1[i]<='9')
{
coe+=s1[i]-'0';
if(s1[i+1]>='0'&&s1[i+1]<='9'){coe*=10;i++;}
else break;
}
coe*=sig;
n1[0]=coe;//暂时存储到0次项
pro=2;//进程2,读取x
}
}
//以下读第二个多项式
for(i=0, coe=0, exp=1, pro=0, sig=1; i<n; i++)
{
if(s2[i]=='x'&&pro!=0) {n2[0]=0; n2[1]=coe; pro=1;}//进程1,计算x的次数
else if(s2[i]=='x'&&pro==0)
{
if(s2[i+1]=='^') {coe=1*sig; pro=1;}
else {coe=1*sig; n2[1]=coe; pro=1;}
}
else if(s2[i]=='^') continue;
else if(pro!=1&&s2[i]=='+') {sig=1;}//加法
else if(pro==1&&s2[i]=='+') {pro=0;sig=1;}
else if(pro!=1&&s2[i]=='-') {sig=-1;}//减法
else if(pro==1&&s2[i]=='-') {pro=0;sig=-1;}
else if(pro==1)
{
exp=0;
while(s2[i]>='0'&&s2[i]<='9')
{
exp+=s2[i]-'0';
if(s2[i+1]>='0'&&s2[i+1]<='9'){exp*=10;i++;}
else break;
}
n2[exp]=coe;
n2[1]=0;
n2[0]=0;
}
else if(pro==0)//进程0,计算x的系数
{
coe=0;
while(s2[i]>='0'&&s2[i]<='9')
{
coe+=s2[i]-'0';
if(s2[i+1]>='0'&&s2[i+1]<='9'){coe*=10;i++;}
else break;
}
coe*=sig;
n2[0]=coe;//暂时存储到0次项
pro=2;//进程2,读取x
}
}
//以下计算结果多项式的系数
int j, ans[101], cnt=0;
for(i=0; i<51; i++)
for(j=0; j<51; j++)
time[i+j]+=n1[i]*n2[j];
for(i=100; i>=0; i--)
if(time[i])
ans[cnt++]=time[i];
for(i=0; i<cnt-1; i++)
printf("%d ",ans[i]);
printf("%d\n",ans[i]);
}
return 0;
}
1046. 单词表
https://acm.ecnu.edu.cn/contest/365/problem/1046/
题解
会stl太简单了,不会的话可以学。不学的话老老实实字符数组,一个一个搜吧。
代码
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b){
return a.compare(b)<0 ? true:false;
}
int main(){
int T;
cin>>T;
getchar();
for(int i = 0; i < T; i++){
vector<string> v;
string s = "";
char ch;
while((ch=getchar())!='\n'){
if(ch < 'a' || ch > 'z'){
int flag = 1;
for(int j = 0; j < v.size(); j++){
if(!v[j].compare(s)){
flag = 0;
break;
}
}
if(flag && s.length())
v.push_back(s);
s = "";
}
else
s += ch;
}
int flag = 1;
for(int j = 0; j < v.size(); j++){
if(!v[j].compare(s)){
flag = 0;
break;
}
}
if(flag && s.length())
v.push_back(s);
sort(v.begin(), v.end(), cmp);
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < v.size(); j++)
cout<<v[j]<<" ";
cout<<endl;
}
return 0;
}
1047. 字串间距
https://acm.ecnu.edu.cn/contest/365/problem/1047/
题解
find和rfind函数,分别找两个字符串的左边第一个索引和右边第一个索引,索引相减比较大小,输出大的。注意特判s1=s2=s的情况。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
scanf("%d", &T);
getchar();
for(int i = 0; i < T; i++){
string s1 = "";
string s2 = "";
string s = "";
cin>>s1>>s2>>s;
string::size_type st1 = s.find(s1);
cout<<"case #"<<i<<":"<<endl;
if(st1 == string::npos){
cout<<0<<endl;
continue;
}
string::size_type st2 = s.find(s2);
if(st2 == string::npos){
cout<<0<<endl;
continue;
}
if(s==s1){
cout<<0<<endl;
continue;
}
int s1p1 = st1;
int s2p1 = st2;
int s1p2 = s.rfind(s1);
int s2p2 = s.rfind(s2);
int len = fabs(s1p1-s2p2)>fabs(s1p2-s2p1)?fabs(s1p1-s2p2)-s1.length():fabs(s1p2-s2p1)-s2.length();
cout<<len<<endl;
}
return 0;
}
1048. Base64编码
https://acm.ecnu.edu.cn/contest/365/problem/1048/
题解
模拟题,string真香。
代码
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
char tb[68] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
string itoa(int n)
{
string ans="";
do{
int t=n%2;
if(t>=0&&t<=9) ans+=t+'0';
else ans+=t-10+'a';
n/=2;
}while(n);
reverse(ans.begin(),ans.end());
while(ans.length()<8)
ans = "0"+ans;
return ans;
}
char atoc(string s){
int tmp = 0;
for(int i = 0; i < s.length()-1; i++)
tmp = tmp*2+s[i]-48;
return tb[tmp];
}
int main(){
int T;
cin>>T;
getchar();
for(int i = 0 ; i < T; i++){
string s = "";
int a[101] = {0};
int alen = 0;
char ch;
while((ch=getchar())!='\n')
a[alen++]=ch;
for(int j = 0; j < alen; j++)
s += itoa(a[j]);
while(s.length()%6)
s += "0";
string ss[1001] = {""};
int sslen = 0;
for(int j = 0; j < s.length()-5; j+=6){
ss[sslen] = s.substr(j, 6);
ss[sslen] = "00" + ss[sslen] + '\0';
sslen++;
}
vector<char> v;
for(int j = 0; j < sslen; j++)
v.push_back(atoc(ss[j]));
while(v.size()%4)
v.push_back('=');
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < v.size(); j++)
cout<<v[j];
cout<<endl;
}
return 0;
}
1050. GPS数据处理
https://acm.ecnu.edu.cn/contest/365/problem/1050/
题解
按照题目提示一步步做就得出答案了。阅读理解题。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
stack<char> st;
int hou, min, sec;
while(s!="END"){
int i = 1;
string tmps = "$GPRMC";
int flag = 1;
for(; i <= 5; i++){
if(s[i]!=tmps[i])
flag = 0;
}
if(!flag){
cin>>s;
continue;
}
i = s.length()-1;
while(s[i]!='*')
st.push(s[i--]);
int cor = 0;
while(!st.empty()){
int tmp;
if(st.top()<='F' && st.top()>='A')
tmp = st.top()-'A'+10;
else
tmp = st.top()-'0';
cor = cor*16+tmp;
st.pop();
}
int res = s[1];
for(int j = 2; j < i; j++)
res ^= s[j];
res %= 65535;
if(res != cor){
cin>>s;
continue;
}
else{
i = 0;
int time = 0;
while(s[i++]!=',');
time = i;
while(s[i++]!=',');
if(s[i]!='A'){
cin>>s;
continue;
}
hou = (s[time]-'0')*10+(s[time+1]-'0')+8;
hou %= 24;
min = (s[time+2]-'0')*10+(s[time+3]-'0');
sec = (s[time+4]-'0')*10+(s[time+5]-'0');
cin>>s;
}
}
if(hou < 10) cout<<0;
cout<<hou<<":";
if(min < 10) cout<<0;
cout<<min<<":";
if(sec < 10) cout<<0;
cout<<sec<<endl;
return 0;
}
1051. 排版
https://acm.ecnu.edu.cn/contest/365/problem/1051/
题解
这题数据看得我火大。字符串结束居然不直接换行,而是多了一连串空格才结束,导致直接cin>>s会找不到回车符,进而无限读取下去。
其余的部分没什么难度,读进来一行字符串,判断前n个字符串加上n-1个空格不超过标准长度,然后算出需要多少个空格。比如abc,123,d,efgh,标准长度为10。那么很明显,智能选前三个,因为加上第四个字符串会超过10。选完前三个,判断出还需要三个空格。有两个空位。那么第一个空位就是3/2个空格,第二个空位就是(3-3/2)/1个空格。按这样的思路填下去。注意特判最后一个空位,一定只能填1个空格。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int perLen;
cin>>perLen;
getchar();
string ss[2001]={""};
int sslen = 0;
char ch;
int strlength = 0;
while((ch=getchar())!='\n'){
if(ch != ' '){
ss[sslen] += ch;
strlength++;
}
else{
if(strlength)
sslen++;
strlength = 0;
}
}
sslen++;
int tmpLen = 0;
vector<string> v;
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < sslen; j++){
int tmpPerLen = perLen;
while(tmpLen+ss[j].length()<=tmpPerLen){
tmpLen += ss[j].length();
v.push_back(ss[j]);
j++;
tmpPerLen--;
if(j>=sslen)
break;
}
int spaceNum = perLen-tmpLen;
for(int k = 0; k < v.size(); k++){
cout<<v[k];
if(j != sslen){
if(k != v.size()-1){
for(int l = 0; l < spaceNum/(v.size()-k-1); l++)
cout<<' ';
spaceNum-=spaceNum/(v.size()-k-1);
}
}
else{
cout<<' ';
}
}
tmpLen = 0;
v.clear();
j--;
cout<<endl;
}
}
return 0;
}
1052. 删除注释
https://acm.ecnu.edu.cn/contest/365/problem/1052/
题解
没搞明白,这题好像有bug,用cout输出会爆炸。
考虑引号内部、转义字符等情况,一个个if判断过去就行了。
代码
#include<stdio.h>
void echo_quote(char c){
char d;
putchar(c);
while ((d = getchar()) != c){
if(d==EOF) return;
putchar(d);
if (d == '\\')
putchar(getchar());
}
putchar(d);
}
void in_comment(){
char c, d;
c = getchar();
if(c==EOF) return;
d = getchar();
if(d==EOF) return;
while (c != '*' || d != '/'){
c = d;
d = getchar();
if(d==EOF) return;
}
}
void start_comment(){
char c, d;
while (c != '\n'){
c=getchar();
if(c==EOF) return;
}
putchar(c);
}
void recomment(char c){
char d;
if (c == '/'){
if ((d = getchar()) == '*'){
if(d==EOF) return;
in_comment();
}
else if (d == '/')
start_comment();
else{
putchar(c);
putchar(d);
}
}
else if (c == '\'' || c == '"')
echo_quote(c);
else
putchar(c);
}
int main(){
char c, d;
while ((c = getchar()) != EOF)
recomment(c);
return 0;
}
1053. 最大分词法
https://acm.ecnu.edu.cn/contest/365/problem/1053/
题解
直接模拟题面给出的方法复杂度为O(n^3),必超时。
我这里的思路是,先将单词表按照长度排序。然后给定start位置,去单词表里从左往右找,找到的第一个就是最长的。然后将字符串消去这个单词。继续找即可。这样复杂度就被降到了O(n^2),一通计算得出,时间不超过0.1s。开冲。
代码
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b){
return a.length()>b.length();
}
int main(){
int n;
cin>>n;
vector<string> tb;
string tmp;
for(int i = 0; i < n; i++){
cin>>tmp;
tb.push_back(tmp);
}
sort(tb.begin(), tb.end(), cmp);
string s;
cin>>s;
int spos = 0;
int epos = 0;
while(s.length()>0){
char c = s[spos];
int flag = 0;
for(int i = 0; i < tb.size(); i++){
if(tb[i][0]!=c)
continue;
else{
if(s.find(tb[i])==spos){
int length = tb[i].length();
for(int j = spos; j < spos+length; j++)
cout<<s[j];
cout<<' ';
flag = 1;
s.erase(spos, length);
break;
}
}
}
if(!flag){
cout<<s[spos]<<' ';
s.erase(spos, 1);
}
}
cout<<endl;
return 0;
}
1054. 听写字符串
https://acm.ecnu.edu.cn/contest/365/problem/1054/
题解
别被super吓到,这题毫无难度。我2分钟就ac了。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
string res = "";
char start;
char ch=getchar();
res += ch;
start = ch;
while((ch=getchar())!='\n'){
if(ch >= start){
res = ch + res;
start = ch;
}
else
res += ch;
}
for(int i = 0; i < res.length(); i++){
if(res[i]<='z' && res[i]>='a')
printf("%c",res[i]-32);
else
printf("%c",res[i]);
}
cout<<endl;
return 0;
}
1073. 计算2的N次方
https://acm.ecnu.edu.cn/contest/365/problem/1073/
不会有人不会做吧?
代码
#include <iostream>
using namespace std;
long long f(long long n, long long m){
if (m == 0) return 1;
else if (m == 1) return n;
else if (!(m%2)) return f(n*n, m/2);
return f(n*n, m/2) * n;
}
int main(){
int T, N;
cin >> T;
for (int i = 0; i < T; i++){
cin >> N;
cout << "case #" << i << ':' << endl;
cout << f(2, N) << endl;
}
return 0;
}
1076. 最小不重复数
https://acm.ecnu.edu.cn/contest/365/problem/1076/
题解
需要一定的找规律能力,手写几个情况就懂了。
先把读进来的数+1,因为是大整数,怎么用数组+1思考一下。
然后从右向左搜,搜到相邻两个一样的数字停下。分类讨论。
如果数字不是9,那么直接令这两位数字+1(比如88767->89767, 11040->12040),然后后面所有的数字填上0101010101……(89767->89010, 12040->12010)做完了。
如果数字是9,令这两位数字前一位+1(比如1099049->1199049),然后前一位后面所有数字填上010101010……(1199049->1101010),然后继续搜索,进入判断。
具体的数学证明我不会写,反正就是有这么个规律,看出来的。如果有大佬愿意写证明,欢迎交流。
代码
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
cout<<"case #"<<i<<':'<<endl;
char ch;
char num[101] = {'\0'};
cin>>(num+1);
num[0] = {'0'};
int rear = strlen(num)-1;
if(rear == 1) {int result = num[1] - 47; cout<<result<<endl; continue;}
for(int j = rear; j >= 0; j--){
if(num[j]!='9') {num[j]++; break;}
else num[j] = '0';
}
int flag = 0;
while(flag != 1){
flag = 1;
int index = 0;
char last = num[0];
for(int j = 1; j <= rear; j++){
if(last == num[j]){
index = j;
flag = 0;
if(last == '9') flag = 2;
break;
}
last = num[j];
}
if(flag == 0){
num[index]++;
int a = 1;
int add = 49;
for(int k = index+1; k <= rear; k++){
add += (-1)*a;
num[k] = add;
a *= -1;
}
flag = 1;
}
if(flag == 2){
index -= 2;
num[index]++;
int a = 1;
int add = 49;
for(int k = index+1; k <= rear; k++){
add += (-1)*a;
num[k] = add;
a *= -1;
}
}
}
if(num[0] == '0') cout<<num+1<<endl;
else cout<<num<<endl;
}
return 0;
}
1106. 安全驾驶
在一单行直线测试车道中有 辆自动驾驶的小车同向行驶。初始时每辆小车有各自的出发位置和恒定速度。
同时开始出发后,若后面的小车追上前面的小车,为了安全则必须降速到与前车相同的速度。最后所有小车都需要到达目的地。
最后一辆小车不想中途降速,希望全程匀速行驶,请找出最后一辆小车在满足条件(全程匀速且保证安全)的情况下最大可能的速度。
https://acm.ecnu.edu.cn/contest/365/problem/1106/
题解
应该没啥难想的,学过面向对象的可以考虑把车子抽象成一个对象,拥有距离,速度,到达终点时间三个成员。挑出到达终点时间最长的,使最后一辆车和这辆车同时抵达终点,求出速度即可。
代码
#include <iostream>
using namespace std;
typedef struct cars{
int k,s;
double time;
}C;
int main(){
int d,n;
cin>>d>>n;
C cars[10001];
double maxT = 0;
for(int i = 0; i < n; i++){
cin>>cars[i].k>>cars[i].s;
cars[i].time = ((double)d-(double)cars[i].k)/(double)cars[i].s;
if(maxT<cars[i].time) maxT = cars[i].time;
}
printf("%.6f\n", (double)d/maxT);
return 0;
}
1107. 矩形个数
在一个由 0、1 元素构成矩阵中,统计至少含有 k 个 1 的矩形的个数(矩形边界平行于矩阵边界)。注意:单个元素也算是一个矩形。
https://acm.ecnu.edu.cn/contest/365/problem/1107/
题解
看到数据规模小于10,我直接进行一个暴力的搜,六重循环10^6次,可以接受。
以左上角和右下角的坐标确定矩形,对于每个确定的矩形进行遍历,统计1的个数,比较累加即可。
代码
#include<iostream>
using namespace std;
int hasOne(int (*a)[11], int r, int c, int k){
int cnt = 0;
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++){
for(int m = 1; m <= r; m++){
for(int n = 1; n <= c; n++){
int sum = 0;
for(int x = i; x <= m; x++){
for(int y = j; y <= n; y++){
if(a[x][y]) sum++;
}
}
if(sum >= k) cnt++;
}
}
}
}
return cnt;
}
int main(){
int T;
cin>>T;
for(int i = 0; i < T; i++){
int r,c,n,k;
cin>>r>>c>>n>>k;
int a[11][11] = {{0}};
for(int j = 0; j < n; j++){
int x,y;
cin>>x>>y;
a[x][y] = 1;
}
cout<<"case #"<<i<<':'<<endl;
cout<<hasOne(a,r,c,k)<<endl;
}
return 0;
}
1108. Weights
题干太长 直接放链接
https://acm.ecnu.edu.cn/contest/365/problem/1108/
题解
输出有点诡异,要输出一串1和0,第一位代表能不能称重量为1的情况,第n位代表能不能称重量为n的情况。理解之后还是很好做的,直接暴力深搜也能做。
我的做法是将一个砝码当两个用,一正一负,然后用之前的partition problem的递归搜索就能做了。
代码
#include<iostream>
using namespace std;
int isSum(int *a, int i, int num, int sum, int length){
if (i == length)
return num == sum ? 1 : 0;
if(isSum(a, i + 1, num, sum, length))
return 1;
if(isSum(a, i + 1, num + a[i], sum, length))
return 1;
return 0;
}
int main(){
int n;
cin>>n;
int w[401];
int cnt = 0;
int sum = 0;
for(int i = 0; i < n; i++){
int tmp;
cin>>tmp;
w[cnt++] = tmp;
w[cnt++] = -tmp;
sum += tmp;
}
for(int i = 1; i <= sum; i++){
cout<<isSum(w, 0, 0, i, cnt);
}
cout<<endl;
return 0;
}
位运算解法(源自Anlore)
#include <iostream>
#include <bitset>
using namespace std;
int main(){
int n;
cin >> n;
int w[n];
int sum = 0;
for(int i = 0; i < n; i++){
cin >> w[i];
sum += w[i];
}
bitset<2048> bit;
for(int i = 0 ;i < n ;i++){
bitset<2048> temp;
temp.set(1024+w[i]-1);
temp.set(1024-w[i]-1);
bit = bit|bit<<w[i]|bit>>w[i]|temp;
}
for(int i = 1024; i < 1024+sum; i++)
cout << bit[i];
return 0;
}
1109. 计算步数
https://acm.ecnu.edu.cn/contest/365/problem/1109/
题解
参照1036
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
long long x, y;
cin>>x>>y;
x = abs(x);
y = abs(y);
unsigned long long res = 0;
while(x || y){
if(x%2 == y%2){
cout<<-1<<endl;
return 0;
}
long long tmpx, tmpy;
if(x%2){
tmpx = (x-1)/2;
x = (x+1)/2;
y/=2;
if(tmpx%2 == y%2){
if(tmpx == 0 && y == 0){
cout<<res+1<<endl;
return 0;
}
if(x%2 == y%2){
cout<<-1<<endl;
return 0;
}
res++;
}
else{
x = tmpx;
res++;
}
}
else{
tmpy = (y-1)/2;
y = (y+1)/2;
x/=2;
if(tmpy%2 == x%2){
if(tmpy == 0 && x == 0){
cout<<res+1<<endl;
return 0;
}
if(y%2 == x%2){
cout<<-1<<endl;
return 0;
}
res++;
}
else{
y = tmpy;
res++;
}
}
}
cout<<res<<endl;
return 0;
}
Online01. 浮点数的表示法
https://acm.ecnu.edu.cn/contest/365/problem/1109/
题解
char指针,指向地址,输出地址的字符,注意格式为02X即可。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
double d;
cin>>d;
int c = sizeof(d);
unsigned char *p = (unsigned char *)&d;
p+=(c-1);
while (c-->1)
printf("%02X-", *p--);
printf("%02X", *p--);
printf("\n");
return 0;
}
Online02. 字符串排序
https://acm.ecnu.edu.cn/contest/365/problem/1110/
题解
没啥难度,定义结构体,包含字符串,长度,数字个数。读入字符串的时候将成员全部处理完毕,写cmp用sort函数排序即可。
注意ch读入,字符串末尾加一个'\0'。
代码
#include <bits/stdc++.h>
using namespace std;
typedef struct String{
char s[101];
int num;
int length;
}S;
bool cmp(S a, S b){
if(a.num != b.num) return a.num < b.num;
else{
if(a.length != b.length) return a.length > b.length;
else{
if(strcmp(a.s, b.s) > 0) return false;
else return true;
}
}
}
int main(){
int n;
cin>>n;
getchar();
S s[101];
for(int i = 0; i < n; i++){
s[i].num = 0;
s[i].length = 0;
}
for(int i = 0; i < n; i++){
char ch;
int cnt = 0;
while((ch=getchar())!='\n'){
s[i].length++;
s[i].s[cnt++] = ch;
if(ch <= '9' && ch >= '0')
s[i].num++;
}
s[i].s[cnt] = '\0';
}
sort(s, s+n, cmp);
for(int i = 0; i < n; i++)
cout<<s[i].s<<endl;
return 0;
}
Online03. 特殊加密
https://acm.ecnu.edu.cn/contest/365/problem/1111/
题解
我建议放弃思考,直接打表。太方便了。看代码就懂了
代码
#include <bits/stdc++.h>
using namespace std;
class Trans{
public:
int a,b;
Trans(){a = 0, b = 0;}
Trans(char ch){
switch(ch){
case 'A': a = 2, b = 1; break;
case 'B': a = 2, b = 2; break;
case 'C': a = 2, b = 3; break;
case 'D': a = 3, b = 1; break;
case 'E': a = 3, b = 2; break;
case 'F': a = 3, b = 3; break;
case 'G': a = 4, b = 1; break;
case 'H': a = 4, b = 2; break;
case 'I': a = 4, b = 3; break;
case 'J': a = 5, b = 1; break;
case 'K': a = 5, b = 2; break;
case 'L': a = 5, b = 3; break;
case 'M': a = 6, b = 1; break;
case 'N': a = 6, b = 2; break;
case 'O': a = 6, b = 3; break;
case 'P': a = 7, b = 1; break;
case 'Q': a = 7, b = 2; break;
case 'R': a = 7, b = 3; break;
case 'S': a = 7, b = 4; break;
case 'T': a = 8, b = 1; break;
case 'U': a = 8, b = 2; break;
case 'V': a = 8, b = 3; break;
case 'W': a = 9, b = 1; break;
case 'X': a = 9, b = 2; break;
case 'Y': a = 9, b = 3; break;
case 'Z': a = 9, b = 4; break;
}
}
};
string tb[10] = {"-----", ".----", "..---", "...--", "....-", ".....", "-....", "--..."
, "---..", "----."};
int main(){
int T;
cin>>T;
getchar();
for(int i = 0; i < T; i++){
Trans t[201];
int cnt = 0;
char ch;
while((ch=getchar())!='\n'){
Trans tmp(ch);
t[cnt++] = tmp;
}
cout<<"case #"<<i<<":"<<endl;
for(int j = 0; j < cnt-1; j++)
cout<<tb[t[j].a]<<"/"<<tb[t[j].b]<<"/";
cout<<tb[t[cnt-1].a]<<"/"<<tb[t[cnt-1].b]<<endl;
}
return 0;
}
1108给出一种bitset的解法
如下
这是什么神仙操作,学学
太牛了太牛了