时间跨度：01-04 17:46:10 - 01-06 23:01:46
关键知识点：高精度，斐波那契数列
部分新增知识点：
- C语言内置函数__builtin__popcount();
- 数字之间的关系，质数的性质（数论？）
T1 标题统计
题目链接：洛谷P5015
题目解析
获取一整行字符串后计算除空格和换行符以外的字符数即可
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
int main()
{
string str;
getline(cin,str);
int cnt = 0;
for(auto i:str)
if(i != ' ' && i != '\n')
cnt++;
printf("%d",cnt);
return 0;
}
T2 Davor
题目链接:洛谷P4956
题目解析
用等差数列求出每星期筹到的金钱总额乘以总周数52，若刚好等于n则输出并中断。
为了满足 x 尽可能大，k 尽可能小，应使x从100开始倒序循环。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
int main()
{
int n;
scanf("%d",&n);
for(int x = 100; x >= 1; x--)
{
for(int k = 1;k < 3000; k++)
{
int cnt = 52 * (x + x+6*k)*7/2;
if(cnt == n)
{
printf("%d\n%d",x,k);
return 0;
}
}
}
return 0;
}
T3 语句解析
题目链接：洛谷P1597
题目解析
按照题面所给的语句格式
变量 := 变量或一位整数;
逐字扫描判断，以分号作为分隔符进行逐句赋值，未赋值的变量以初始值0作为终值。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
int main()
{
string str;
cin >> str;
int a = 0,b = 0,c = 0;
for(int i = 0; i < str.length(); i++)
{
if(str[i] == 'a')
{
int j = i;
while(str[j] !=';')j++;
if(str[j-1] >= '0' && str[j-1] <= '9')
a = (str[j-1]-'0');
else
{
if(str[j-1] == 'b')
a = b;
else if(str[j-1] == 'c')
a = c;
}
i = j;
}
else if(str[i] == 'b')
{
int j = i;
while(str[j] !=';')j++;
if(str[j-1] >= '0' && str[j-1] <= '9')
b = (str[j-1]-'0');
else
{
if(str[j-1] == 'a')
b = a;
else if(str[j-1] == 'c')
b = c;
}
i = j;
}
else if(str[i] == 'c')
{
int j = i;
while(str[j] !=';')j++;
if(str[j-1] >= '0' && str[j-1] <= '9')
c = (str[j-1]-'0');
else
{
if(str[j-1] == 'a')
c = a;
else if(str[j-1] == 'b')
c = b;
}
i = j;
}
}
printf("%d %d %d",a,b,c);
return 0;
}
T4 数楼梯
题目链接：洛谷P1255
题目解析
本题关键知识点：高精度，斐波那契数列
从前几阶楼梯可以发现，上到每节楼梯的走法数分别为1,2,3,5，……，显然就是去掉第一项后的斐波那契列
但题目数据范围N <= 5000,斐波那契数列的值呈指数级爆炸增长，因而要使用高精度防止数据溢出。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
const int MAXN = 5010;
int a[MAXN],b[MAXN],c[MAXN];
int main()
{
int n;
scanf("%d",&n);
if(n < 3)
printf("%d",n);
else
{
int cnt = 1;
a[1] = 1,b[1] = 2;
for(int i = 3; i <= n; i++)
{
for(int j = 1; j <= cnt; j++)
c[j] = a[j]+b[j];
for(int j = 1; j <= cnt; j++)
{
if(c[j] > 9)
{
c[j+1] += c[j]/10;
c[j] %= 10;
if(j+1 > cnt)
cnt++;
}
}
for(int j = 1; j <= cnt; j++)
a[j] = b[j];
for(int j = 1; j <= cnt; j++)
b[j] = c[j];
}
for(int i = cnt;i > 0;i--)
printf("%d",b[i]);
}
return 0;
}
T5 分数线划定
题目链接：洛谷P1068
题目解析
用结构体存储每名选手的报名号和成绩，然后依照提议解题即可，要注意cmp函数的写法。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
struct peo
{
int id,score;
};
bool cmp(const peo &p1,const peo &p2)
{
if(p1.score != p2.score)
return p1.score > p2.score;
else
return p1.id < p2.id;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int num = m * 1.5;
struct peo p[n];
for(int i = 0; i < n; i++)
scanf("%d %d",&p[i].id,&p[i].score);
sort(p,p+n,cmp);
int line = p[num-1].score,cnt = 0;
for(int i = 0; p[i].score >= line; i++)
cnt++;
printf("%d %d\n",line,cnt);
for(int i = 0; i < cnt; i++)
printf("%d %d\n",p[i].id,p[i].score);
return 0;
}
T6 涂国旗
题目链接：洛谷P3392
题目解析
预处理存储每行R/W/B三种颜色的块数，之后暴力O(n^2)枚举前两种颜色的行数(第三种颜色为剩下的行数)，用m减去某行某颜色的块数既得该行的成本，取得每次成本总和的最小值即可。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
struct color
{
int white,blue,red;
};
int main()
{
int n,m;
scanf("%d %d",&n,&m);
char ch[n][m];
struct color c[n];
for(int i = 0; i < n; i++)
{
int w = 0,b = 0,r = 0;
for(int j = 0; j < m; j++)
{
scanf(" %c",&ch[i][j]);
switch(ch[i][j])
{
case 'W':
w++;
break;
case 'R':
r++;
break;
case 'B':
b++;
break;
}
}
c[i].white = w;
c[i].blue = b;
c[i].red = r;
}
int cnt = 1e7;
for(int i = 1; i <= n-2; i++)
{
for(int j = i+1; j <= n-1; j++)
{
int sum = 0;
for(int k = 1; k <= i; k++)
sum += (m-c[k-1].white);
for(int k = i+1; k <= j; k++)
sum += (m-c[k-1].blue);
for(int k = j+1; k <= n; k++)
sum += (m-c[k-1].red);
cnt = min(cnt,sum);
}
}
printf("%d",cnt);
return 0;
}
T7 拼数
题目链接：洛谷P1012
题目解析
将所有数字按字典序顺序降序排列后拼接即可。要注意cmp函数不能直接判断两字符串
return s1 > s2;
return s1+s2 > s2+s1;
详见代码中注释
AC代码
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
//typedef long long ll;
vector<string> v;
bool cmp(const string &s1,const string &s2)
{
/*
若用s1 > s2,则结果为321 32 ->32132,但最大应为32321
使用s1+s2 > s2+s1则可避免这种32132>32321的情况
*/
return s1+s2 > s2+s1;
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 0;i < n;i++)
{
string str;
cin >> str;
v.push_back(str);
}
sort(v.begin(),v.end(),cmp);
for(auto i:v)
cout << i;
return 0;
}
T8 烤鸡
题目链接：洛谷P2089
题目解析
直接暴力枚举10种配料的所有搭配方案，若质量总和等于n则保存，等待输出。注意每种配料的质量都不能为0。
(由于配料质量和的最大值只有30，所以n > 30的可以直接输出0)
AC代码
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
//typedef long long ll;
vector<vector<int> > v;
vector<int> vs;
int main()
{
int n;
scanf("%d",&n);
int cnt = 0;
for(int q = 1;q <= 3;q++)
for(int w = 1;w <= 3;w++)
for(int e = 1;e <= 3;e++)
for(int r = 1;r <= 3;r++)
for(int t = 1;t <= 3;t++)
for(int y = 1;y <= 3;y++)
for(int u = 1;u <= 3;u++)
for(int i = 1;i <= 3;i++)
for(int o = 1;o <= 3;o++)
for(int p = 1;p <= 3;p++)
if(q+w+e+r+t+y+u+i+o+p == n)
{
vs.push_back(q);
vs.push_back(w);
vs.push_back(e);
vs.push_back(r);
vs.push_back(t);
vs.push_back(y);
vs.push_back(u);
vs.push_back(i);
vs.push_back(o);
vs.push_back(p);
v.push_back(vs);
vs.clear();
cnt++;
}
printf("%d\n",cnt);
for(auto i:v)
{
for(auto j:i)
printf("%d ",j);
printf("\n");
}
return 0;
}
T9 独木桥
题目链接：洛谷P1007
题目解析
首先，不用考虑题目中的这一因素的影响：
但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。
引用洛谷题解中很形象的两个例子：
首先自行脑补一下，假装你正在20000米高空的轰炸机上用高倍显微镜望远镜默默欣赏士兵离开，你会发现什么东西？一堆花花绿绿的迷彩服在移动。（不是鬼片！不是鬼片！不是鬼片！重要的事情说三遍）
那么当两个士兵撞在一起时，从你的视角看会发生什么？当然他们认为他们都掉头了，但因为你在特高的地方，你会认为他们“穿过”了对方。换言之，这与他们相互穿过并没有任何区别。
两个人相遇转身，相当于交换灵魂后继续走
那么问题就很简单了，最大值就是最靠近端点的两个人各自向对方方向走下桥,时间较长的那个人的时间，最小值就是所有人走完桥的时间的最小值的最大值。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
int main()
{
int l,n;
scanf("%d %d",&l,&n);
int pos[n]={0};
for(int i = 0;i < n;i++)
scanf("%d",&pos[i]);
sort(pos,pos+n,greater<int>());
int ma = max(pos[0],l-pos[n-1]+1);
int mi = 0;
for(int i = 0;i < n;i++)
{
int tmp = min(pos[i],l-pos[i]+1);
mi = max(tmp,mi);
}
printf("%d %d",mi,ma);
return 0;
}
T10 First Step (ファーストステップ)
题目链接：洛谷P3654
题目解析
枚举每个可站点，判断该点向右方和向下方各有多少种站位方式
要注意k=1的情况下，横着站和竖着站一样，因而要进行特判，此时站位方式数量就是可站点的数量。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
int main()
{
int r,c,k;
scanf("%d %d %d",&r,&c,&k);
int po = 0;
char gym[r][c];
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
{
scanf(" %c",&gym[i][j]);
if(gym[i][j] == '.')
po++;
}
if(k == 1)
{
printf("%d",po);
return 0;
}
int cnt = 0,sum = 0;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
if(gym[i][j] == '.')
{
if(i < r-1)
{
sum = 0;
for(int q = j; q < c; q++)
{
if(gym[i][q] == '.')
sum++;
else
break;
if(sum == k)
{
cnt++;
break;
}
}
sum = 0;
for(int q = i; q < r; q++)
{
if(gym[q][j] == '.')
sum++;
else
break;
if(sum == k)
{
cnt++;
break;
}
}
}
else
{
sum = 0;
for(int q = j; q < c; q++)
{
if(gym[i][q] == '.')
sum++;
else
break;
if(sum == k)
{
cnt++;
break;
}
}
}
}
}
}
printf("%d",cnt);
return 0;
}
T11 蜜蜂路线
题目链接：洛谷P2437
题目解析
类似题目 T4数楼梯：洛谷P1255
本题需用到高精度和斐波那契数列
不同的是本题中最终结果并不是从斐波那契数列第一项加起，它的起始项(左端点)是变化的。
AC代码
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
//typedef long long ll;
const int MAXN = 5010;
int a[MAXN]= {1,1},b[MAXN]= {1},c[MAXN];
int main()
{
int m,n;
scanf("%d %d",&m,&n);
for(int i = m+1; i <= n; i++)
{
for(int j = 0; j <= a[0]; j++)
c[j] = a[j];
for(int j = 1; j <= a[0]; j++)
{
a[j] += b[j];
a[j+1] += a[j]/10;
a[j] %= 10;
}
while(a[a[0]+1]>0)
a[0]++;
memset(b,sizeof(b),0);
for(int j = 0; j <= c[0]; j++)
b[j] = c[j];
}
for(int i = a[0]; i >= 1; i--)
printf("%d",a[i]);
return 0;
}
T12 最大公约数和最小公倍数问题
题目链接：洛谷P1029
题目解析
以x,y为端点进行O(n2) 枚举,由于本题数据范围是105,为了防止TLE需要进行优化，只用枚举max(x,y)的所有因子即可。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
//typedef long long ll;
vector<int> v;
void getnum(int a);
int main()
{
int x,y;
scanf("%d %d",&x,&y);
getnum(max(x,y));
int cnt = 0,size = v.size();
for(int i = 0;i < size;i++)
{
for(int j = size-1;j >= 0;j--)
{
int gnum = __gcd(v[i],v[j]);
int LCD = (v[i] * v[j]) / gnum;
if(gnum == x && LCD == y)
cnt++;
}
}
printf("%d",cnt);
return 0;
}
void getnum(int a)
{
for(int i = 1;i <= a;i++)
if(a % i == 0)
v.push_back(i);
}
T13 种田
题目链接：洛谷P2660
题目解析
类似题目 第四周题单-统计方形：洛谷P2241
不同的是，上题是统计所有方形的数量，而这题是每次切割最大正方形，每次以最短边为边长切割，体力值即为每次所切割的正方形的周长之和。但单单这样写会在最后一个测试点被10^16的数据卡TLE，只能拿90分，因而要进行优化，不能一个正方形一个正方形的切，要一次切多个，也就是切max(x,y)/min(x,y)个。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
scanf("%lld %lld",&n,&m);
ll res = 0;
while(n != 0 && m != 0)
{
ll mi = min(n,m);
if(n < m)
{
res += 4 * (m/mi) * mi;
m %= mi;
}
else
{
res += 4 * (n/mi) * mi;
n %= mi;
}
}
printf("%lld",res);
return 0;
}
T14 混合牛奶 Mixing Milk
题目链接：洛谷P1208
题目解析
用结构体存储每位农民的单价和最大量，按单价从低到高进行排序，依次购买直至购买量等于所需量时即求出最小费用。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
struct farmer{
int price,sum;
};
bool cmp(const farmer &f1,const farmer &f2)
{
return f1.price < f2.price;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
struct farmer f[m];
for(int i = 0;i < m;i++)
scanf("%d %d",&f[i].price,&f[i].sum);
sort(f,f+m,cmp);
int su = 0,money = 0;
for(int i = 0;i < m;i++)
{
if(su + f[i].sum <= n)
{
su += f[i].sum;
money += f[i].price * f[i].sum;
}
else
{
money += f[i].price * (n - su);
break;
}
}
printf("%d",money);
return 0;
}
T15 排队
题目链接：洛谷P5412
题目解析
结构体存储按身高从矮到高排序，最后用cout输出即可。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
struct stu
{
int sex;
double height;
};
bool cmp(const stu &s1,const stu &s2)
{
return s1.height < s2.height;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
struct stu s[n];
for(int i = 0; i < n; i++)
scanf("%d",&s[i].sex);
for(int i = 0; i < n; i++)
scanf("%lf",&s[i].height);
sort(s,s+n,cmp);
for(int i = 0; i < n; i++)
if(s[i].sex == 0)
cout << s[i].height << ' ';
printf("\n");
for(int i = 0; i < n; i++)
if(s[i].sex == 1)
cout << s[i].height << ' ';
printf("\n");
}
return 0;
}
T16 小A的糖果
题目链接：洛谷P3817
题目解析
从左到右依次遍历，若左右之和大于x则将右侧数减去两数之和与x的差 ，结果即为每次该差的总和。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,x;
scanf("%lld %lld",&n,&x);
ll num[n] = {0};
for(int i = 0;i < n;i++)
scanf("%lld",&num[i]);
ll cnt = 0;
for(ll i = 0;i < n-1;i++)
{
if(num[i] + num[i+1] > x)
{
cnt += num[i]+num[i+1]-x;
num[i+1] -= num[i]+num[i+1]-x;
}
}
printf("%lld",cnt);
return 0;
}
T17 阶乘之和
题目链接：洛谷P1009
题目解析
高精度加法与高精度乘法结合
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
const int MAXN = 2e3;
int a[MAXN]= {1},b[MAXN];
void plu(int a[],int b[])
{
int more = 0;
for(int i = 0; i < 1000; i++)
{
b[i] += a[i] + more;
more = b[i]/10;
b[i] %= 10;
}
}
void mul(int a[],int b)
{
int more = 0;
for(int i = 0; i < 1000; i++)
{
a[i] = a[i] * b + more;
more = a[i]/10;
a[i] %= 10;
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
mul(a,i);
plu(a,b);
}
int flag = 0;
for(int i = 999; i >= 0; i--)
{
if(b[i])
flag = 1;
if(flag)
printf("%d",b[i]);
}
return 0;
}
T18 找筷子
题目链接：洛谷P1469
题目解析
利用位运算异或的性质即可，偶数个相同的数异或结果为0，因而将所有筷子长度异或起来的结果即为落单的筷子的长度。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
int main()
{
int n;
scanf("%d",&n);
int len,res;
for(int i = 0;i < n;i++)
{
scanf("%d",&len);
if(i > 0)
res ^= len;
else if(i == 0)
res = len;
}
printf("%d",res);
return 0;
}
T19 两只塔姆沃斯牛 The Tamworth Two
题目链接：洛谷P1518
题目解析
结构体存储坐标和方向，不断循环即可，若某次移动结束后坐标重合即相遇，输出时间（即循环次数），若循环次数过大时（例10^6次）仍未相遇，即可判定永远不会相遇。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
char map[10][10];
struct farmer
{
int x,y;
char dire = 'n';//East South West North
} f;
struct cow
{
int x,y;
char dire = 'n';
} c;
int main()
{
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
{
scanf(" %c",&map[i][j]);
if(map[i][j] == 'F')
{
f.x = i;
f.y = j;
}
else if(map[i][j] == 'C')
{
c.x = i;
c.y = j;
}
}
int cnt = 0;
while(!(f.x == c.x && f.y == c.y))
{
switch(f.dire)
{
case 'n':
if(f.x != 0)
{
if(map[f.x-1][f.y] != '*')
f.x--;
else
f.dire = 'e';
}
else
f.dire = 'e';
break;
case 'e':
if(f.y != 9)
{
if(map[f.x][f.y+1] != '*')
f.y++;
else
f.dire = 's';
}
else
f.dire = 's';
break;
case 's':
if(f.x != 9)
{
if(map[f.x+1][f.y] != '*')
f.x++;
else
f.dire = 'w';
}
else
f.dire = 'w';
break;
case 'w':
if(f.y != 0)
{
if(map[f.x][f.y-1] != '*')
f.y--;
else
f.dire = 'n';
}
else
f.dire = 'n';
break;
}
switch(c.dire)
{
case 'n':
if(c.x != 0)
{
if(map[c.x-1][c.y] != '*')
c.x--;
else
c.dire = 'e';
}
else
c.dire = 'e';
break;
case 'e':
if(c.y != 9)
{
if(map[c.x][c.y+1] != '*')
c.y++;
else
c.dire = 's';
}
else
c.dire = 's';
break;
case 's':
if(c.x != 9)
{
if(map[c.x+1][c.y] != '*')
c.x++;
else
c.dire = 'w';
}
else
c.dire = 'w';
break;
case 'w':
if(c.y != 0)
{
if(map[c.x][c.y-1] != '*')
c.y--;
else
c.dire = 'n';
}
else
c.dire = 'n';
break;
}
cnt++;
if(cnt > 1e6)
{
printf("0");
return 0;
}
}
printf("%d",cnt);
return 0;
}
T20 编码
题目链接：洛谷P1246
题目解析
暴力枚举判断是否相等即可，要注意字母按升序排列，也就是不可能出现zoo之类的单词
刚刚才发现我读入字符串写的竟然是scanf("%s",&str);竟然还AC了，离谱，编译器之前竟然没报警告
AC代码
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
//typedef long long ll;
int main()
{
int cnt = 1;
char str[7],s[7];
scanf("%s",str);
for(char i = 'a'; i <= 'z'; i++)
{
s[1] = '\0';
s[0] = i;
if(strcmp(str,s) == 0)
{
printf("%d",cnt);
return 0;
}
cnt++;
}
for(char i = 'a'; i <= 'y'; i++)
for(char j = i+1; j <= 'z'; j++)
{
s[2] = '\0';
s[1] = j;
s[0] = i;
if(strcmp(str,s) == 0)
{
printf("%d",cnt);
return 0;
}
cnt++;
}
for(char i = 'a'; i <= 'x'; i++)
for(char j = i+1; j <= 'y'; j++)
for(char k = j+1; k <= 'z'; k++)
{
s[3] = '\0';
s[2] = k;
s[1] = j;
s[0] = i;
if(strcmp(str,s) == 0)
{
printf("%d",cnt);
return 0;
}
cnt++;
}
for(char i = 'a'; i <= 'w'; i++)
for(char j = i+1; j <= 'x'; j++)
for(char k = j+1; k <= 'y'; k++)
for(char q = k+1; q <= 'z'; q++)
{
s[4] = '\0';
s[3] = q;
s[2] = k;
s[1] = j;
s[0] = i;
if(strcmp(str,s) == 0)
{
printf("%d",cnt);
return 0;
}
cnt++;
}
for(char i = 'a'; i <= 'v'; i++)
for(char j = i+1; j <= 'w'; j++)
for(char k = j+1; k <= 'x'; k++)
for(char q = k+1; q <= 'y'; q++)
for(char w = q+1; w <= 'z'; w++)
{
s[5] = '\0';
s[4] = w;
s[3] = q;
s[2] = k;
s[1] = j;
s[0] = i;
if(strcmp(str,s) == 0)
{
printf("%d",cnt);
return 0;
}
cnt++;
}
for(char i = 'a'; i <= 'u'; i++)
for(char j = i+1; j <= 'v'; j++)
for(char k = j+1; k <= 'w'; k++)
for(char q = k+1; q <= 'x'; q++)
for(char w = q+1; w <= 'y'; w++)
for(char e = w+1; e <= 'z'; e++)
{
s[6] = '\0';
s[5] = e;
s[4] = w;
s[3] = q;
s[2] = k;
s[1] = j;
s[0] = i;
if(strcmp(str,s) == 0)
{
printf("%d",cnt);
return 0;
}
cnt++;
}
printf("0");
return 0;
}
T21 帮贡排序
题目链接：洛谷P1786
题目解析
按照题意即可，要注意调整职位和输出时的排序方式不同，要写两个cmp函数，调整职位和输出前要分别调用一次sort函数。
一定要注意职位的大小写，不然一个字母的差别就是全WA与全AC的差别
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
enum prof
{
BangZhong,JingYing,TangZhu,ZhangLao,HuFa,FuBangZhu,BangZhu
};
struct org
{
string name;
int pro,con,level,index;
};
bool cmp1(const org &o1,const org &o2)
{
if(o1.con != o2.con)
return o1.con > o2.con;
else
return o1.index < o2.index;
}
bool cmp2(const org &o1,const org &o2)
{
if(o1.pro != o2.pro)
return o1.pro > o2.pro;
else if(o1.level != o2.level)
return o1.level > o2.level;
else
return o1.index < o2.index;
}
int bz,fbz,hf,zl,tz,jy,baz;
int main()
{
int n;
scanf("%d",&n);
struct org o[n];
for(int i = 0; i < n; i++)
{
string pr;
cin >> o[i].name >> pr;
scanf("%d %d",&o[i].con,&o[i].level);
o[i].index = i;
if(pr == "BangZhu")
o[i].pro = BangZhu;
else if(pr == "FuBangZhu")
o[i].pro = FuBangZhu;
else if(pr == "HuFa")
o[i].pro = HuFa;
else if(pr == "ZhangLao")
o[i].pro = ZhangLao;
else if(pr == "TangZhu")
o[i].pro = TangZhu;
else if(pr == "JingYing")
o[i].pro = JingYing;
else if(pr == "BangZhong")
o[i].pro = BangZhong;
}
sort(o,o+n,cmp1);
for(int i = 0; i < n; i++)
{
if(o[i].pro <= HuFa && o[i].name != "absi2011")
{
if(hf < 2)
{
o[i].pro = HuFa;
hf++;
}
else if(zl < 4)
{
o[i].pro = ZhangLao;
zl++;
}
else if(tz < 7)
{
o[i].pro = TangZhu;
tz++;
}
else if(jy < 25)
{
o[i].pro = JingYing;
jy++;
}
else
{
o[i].pro = BangZhong;
baz++;
}
}
}
sort(o,o+n,cmp2);
for(auto i:o)
{
cout << i.name << " ";
switch(i.pro)
{
case BangZhu:
printf("BangZhu");/*打成Bangzhu导致全WA，改正后全AC*/
break;
case FuBangZhu:
printf("FuBangZhu");
break;
case HuFa:
printf("HuFa");
break;
case ZhangLao:
printf("ZhangLao");
break;
case TangZhu:
printf("TangZhu");
break;
case JingYing:
printf("JingYing");
break;
case BangZhong:
printf("BangZhong");
break;
}
printf(" %d\n",i.level);
}
return 0;
}
T22 数列找不同
题目链接：洛谷P3901
题目解析
预处理不断循环找出每个区间内各数互不相同的最长区间，每次固定右端点找出最小左端点，若询问的左端点小于对应的最小左端点即可判断存在相同的数。
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//typedef long long ll;
const int MAXN = 1e6;
int num[MAXN],a[MAXN];//num[i]->以第i个数为右端点时左端点的最小值
int main()
{
int n,q;
scanf("%d %d",&n,&q);
int k;
for(int i = 1; i <= n; i++)
{
scanf("%d",&k);
num[i] = max(num[i-1],a[k]+1);
a[k] = i;
}
while(q--)
{
int l,r;
scanf("%d %d",&l,&r);
if(num[r] <= l)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
T23 倒水
题目链接：洛谷P1582
题目解析
新增知识点：
C语言内置函数： __builtin__popcount(); 返回参数在二进制下1的个数
复习知识点：
位运算中 n&-n 表示n在二进制中最后一个1所代表的值
因为所有的水都是由两份相同的水合并而成的，因此每瓶水的体积一定是2^i（i ∈ N）升，最后保留k个瓶子，那么最后总的升数的二进制表示中，1的个数一定<=k。
| 合并前 | 二进制 | 合并后 |
|---|---|---|
| 1个瓶子 | 1 | 1个瓶子 |
| 2个瓶子 | 10 | 2个瓶子 |
| 3个瓶子 | 11 | 3个瓶子 |
| 4个瓶子 | 100 | 4个瓶子 |
| 5个瓶子 | 101 | 5个瓶子 |
| 6个瓶子 | 110 | 6个瓶子 |
| 7个瓶子 | 111 | 7个瓶子 |
| 8个瓶子 | 1000 | 8个瓶子 |
| …… | …… | …… |
由图显然，n个有水的瓶子，最后合并成的瓶子个数，就是这个数转成二进制1的个数。
AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
//typedef long long ll;
int main()
{
int n,k,res = 0;
scanf("%d %d",&n,&k);
while(__builtin_popcount(n) > k)
{
res += n&(-n);
n += n&(-n);
}
printf("%d",res);
return 0;
}
T24 Cities and States S
题目链接：洛谷P3405
题目解析
题目中特殊的一对类似于成对的飞地，显然在一对飞地中，其中一方的CS（City State）代码等于另一方的SC（State City）代码，进而存储一方的CS就可被另一方的SC吻合读取，特殊对数加一。要注意City代码与State代码相等的本地特殊城市。
AC代码
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
//typedef long long ll;
map<string,int> mp;
int main()
{
int n;
scanf("%d",&n);
int cnt = 0;
string city,state,cs,sc;
for(int i = 0;i < n;i++)
{
cin >> city >> state;
cs = city.substr(0,2) + state;
sc = state + city.substr(0,2);
cnt += mp[sc];
if(cs == sc)
cnt -= mp[cs];
mp[cs]++;
}
printf("%d",cnt);
return 0;
}
T25 Dreamoon and Sets
题目链接：洛谷CF476D
题目解析
第一道紫题
我觉得我得重读小学二年级
枚举失败的我从洛谷题解中获取到了一些奇怪的知识：
互质的一组数中a,b,c,d的值越接近,就能使最大值越小。
相邻的两个正整数数是互质的，相邻的两个奇数也是互质的。
连续n个正整数必有一个数能被n整除，不考虑1,2
- a,b,c,d互质，所以a,b,c,d中最多有一个偶数 为了让四个数的值更接近，我们不妨先假设有1个偶数，3个奇数。
- 进一步转换，我们可以将a,b,c,d设为x,x+m1,x+m2,x+m3.
- 因此我们先尝试令m1=1,m2=2,即四元组中前三个数为x,x+1,x+2。由于四元组中最多只有一个偶数，故x为奇数，根据以上易证的结论可知这三个数一定互质。
- 考虑x是奇数，那么(x,x+1,x+2,x+4)一定满足要求，且不能更小。考虑x是偶数，那么(x,x+1,x+3,x+5)不一定满足要求，而且不能更小。显然x取奇数时是最优的。
- 最大数为 (n*6-1)*k
- 第一个数从1开始选，同时要保证所以四元组的第一个数为基数，每隔6个确定一个x就好了。x的通项公式即为(i-1)*6+1
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
printf("%d\n",(n*6-1) * k);
for(int i = 1;i <= n;i++)
{
int num = (i-1)*6+1;
printf("%d %d %d %d\n",num*k,(num+1)*k,(num+2)*k,(num+4)*k);
}
return 0;
}
Q.E.D.