难过的一天，从在普及组淦不过初一初二开始。
T1：【欢愉】（传送门）
题意：现在有A 名男性，B 名女性，以及C 名可以为男性也可以为女性的生物。
至多能够产生多少对男女呢？
水题，你想怎么做就怎么做。
先判断A、B之间可以直接产生几对男女，再用C去配对。最后C如果还有剩，可以除以2算出又能配出几对男女。
T2：【魔法】（传送门）
题意：给你两组数列（长度可一可不一），总和相同，将他们各自分成k段，要求对应分段的和相等。求k的最大值。
不难看出，k有且只有一个答案，所以，模拟。
f1、f2分别记分段的和，一个固定，另一个一直向后加。当两个相等时，证明此处该分段，答案加加，f1、f2清零。当向后加的那个大于固定的那个时，固定的向后加直到再次大于前面那个。反复上面的操作。
好像有点绕······（自行理解吧）
T3：【指引】（传送门）
省常州Day4原题，但是改了数据，n<=1000；（原题解戳这）
所以可以直接打一个n方的贪心。对于每个旅客，找所有可行的出口中列最小。
嗯，这么简单的题我还是炸了，该好好好反省了。
T4：【碎片】（传送门）
常州原题，一个复杂的搜索。（原题解戳这）
回归pj组的感觉真好。
T1：【水题】（传送门）
意如其题，名副其实的水题。
有n个硬币，初始状态正面朝上；进行m次翻转，反转规则：第i次翻转序号为i的约数的硬币。随便for一下就可以解决了（毕竟n，m都不大于300）。然后翻转可以用异或。（0 xor 1=1；1 xor 1=0）
T2：【虚无】（传送门）
有n种物品，每种物品数量无限，代价为Xi/Yi（即拾取Yi 件这种物品总共需要花费Xi 的代价）。问取m件产品最小的代价。
数据范围：
看着是不是很像完全背包，场上忘记动规的我抱着尝试的心态打了40分的算法+贪心。
竟然AC了······贪心：只选择1种物品，取m件，算出代价比较。
世事无常啊
T3：【空洞】（传送门）
题意：求出第K 小的数位和为10 的数。
也是很简单的一题，直接枚举，然后打一个函数（也可以不用直接放在里面）求数位和，等于10的话有一个数计数++知道这个数等于k就好了。
枚举范围：因为k<=10000，所以就一个一个试，因为范围若是小了是没有答案的，直到出来答案（当k=10000的时候答案是10800100八位数），然后再定比10800100大一点的数就好了（看心情）。然后时间只有0.5秒，我担心会超时，加了一个小小的优化，i每次+9 instead of ++，因为我发现从19开始之后的每一个数位和为10的数都可以通过+9得到，不会遗漏。
T4：【荒诞】（传送门）
这是在常州做过的原题，就不多讲了。（想看的戳这）
主要是我在测大数据的时候竟然和他给的答案不一样，这就很怀疑人生了，但交上去却AC了，是我的问题吗，迷······
————伪AK
在桌面上有一排硬币，共N枚，标号分别从1至N，每一枚硬币均为正面朝上。现在进行M次翻转操作，第i次翻转的规则是将标号为i的约数的硬币进行一次翻转。（正面向上的被翻转为反面向上，反之亦然）。求M次翻转后，正面朝上的硬币数量。
solution：
真*水题
可以按照题意模拟，对1-m中每个i枚举约数并相应翻转，O(M√M)，随随便便就过。
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=m;i++){
for(int j=1;j*j<=i;j++){
if(i%j==0){
if(j<=n) a[j]^=1;
if(i/j!=j&&i/j<=n) a[i/j]^=1;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!a[i]) ans++;
}
printf("%d\n",ans);
然而实际上这道题完全可以用O(N)做出来，因为对于1-n中的每个编号i的硬币，翻转次数实际上为m/i，所以将翻转次数m/i%2即可判断硬币正反。
2
3
4
5
6
7
for(int i=1;i<=n;++i)
{
t[i]=m/i%2;
if(!t[i]) ans++;
}
printf("%d",ans);
solution：
真^水题x2
因为每种物品数量不限，所以m次全部选择代价最小的物品就可以了。
一朝被蛇咬，十年怕井绳，所以为了防炸浮点数，特意先将x*m再除y（然并卵）。
2
3
4
5
6
7
8
9
10
11
12
13
14
double mins=999999;//最小代价
int mx,my;//代价最小的xi和yi
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
double s=x*1.0/y;//算出一件物品的代价
if(s<mins){
mx=x;my=y;
mins=s;
}
}
mx*=m;//先将x*m再除y
printf("%.10lf",mx*1.0/my);
请求出第K小的数位和为10 的数。
solution：
1）答案最大在 10^7 级别，暴力枚举1-10^7的每个数，判断和是否为0，
2
3
4
5
6
7
8
9
10
if((i % 10) + (i / 10 % 10) + (i / 100 % 10) + (i / 1000 % 10) + ( i / 10000 % 10) + (i / 100000 % 10) + (i / 1000000 % 10) + (i / 10000000 % 10)== 10) {
//判断每一位加起来是否等于10
count ++;
if(count == k){
printf("%d",i);
break;
}
}
}//PS:挺简洁的，但是这代码看着有点<del>滑稽</del>
另一种写法：
2
3
4
5
6
7
8
9
10
11
12
13
14
{
int k=i,Sum=0;
while(k!=0)
{
Sum+=k%10;
k/=10;
}//判断每一位加起来是否等于10
if(Sum==10) tot++;
if(N==tot){
printf("%d",i);
return 0;
}
}
2）类似全排列，用搜索一位一位填数（昨天讲DFS，入戏太深……）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int m=9;
int t[20];
void dfs(int n,int s){
if(n==0){
long long sum=0;
for(int i=1;i<=m;i++){
sum+=t[i];
}
if(sum==10) ans++;
if(ans>=k){
sum=0;
long long f=1;
for(int i=1;i<=m;i++){
sum+=t[i]*f;
f*=10;
}
printf("%lld\n",sum);
flag=0;
}
return;
}
for(int i=0;i<=9&&i<=10-s;i++){
t[n]=i;
dfs(n-1,s+i);
if(!flag) return;
}
}
int main(){
scanf("%d",&k);
dfs(m,0);
return 0;
}//多么<del>漂亮</del>的搜索模板……（逃
solution：
因为前缀的字典序随长度递增，所以前缀数组第i位的下标为i，即ANS=1~n的平方和（记得long long）。
2
3
4
5
ll sum=0;
for(long long i=1;i<=len;i++)
sum=(sum+i*i)%mod;
printf("%lld\n",sum);
小X 是一个实力不强的OIer，他一共在N 场比赛中失败过。
每一场比赛持续的时间可以用一个数轴上的区间[Li,Ri]来表示，同一时间可
能会有多场比赛。
退役后，小X 回忆起自己失败的OI 历程，他选择了M 场失败的比赛，定义
这M 场比赛持续时间的交集长度为这M 场比赛的失败程度。
小X 希望选出一组失败程度最高的M 场比赛。
————But I'll be fine.
n组数据，判断一个数ai是否能写出若干个阶乘的乘积
1≤n≤100000， ai≤10^18。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
f[0]=1;
for(int i=1;i<=20;i++){
f[i]=f[i-1]*i;
}//计算20以内的阶乘（阶乘最大到20不会炸longlong ）
s.insert(1);
for(set<long long>::iterator i=s.begin();i!=s.end();i++){
for(int j=2;j<=20;j++){
if(Size/(*i)>=f[j]){ //如果阶乘之积小于10^18则插入
s.insert((*i)*f[j]); //set不会重复
}
}
}
int T;read(T);
while(T--){
long long n;read(n);
if(s.find(n)!=s.end()) printf("YES\n"); //判断是否是阶乘之积
else printf("NO\n");
}
return 0;
}
给定一个01矩阵，第n行高度为1，第1行高度为n。
求其中有几个连通块的高度≥k
01矩阵的行数，列数 n，m <= 20
水题。
用bfs求出高度大于等于k的连通块个数。
一个长为n，宽为m的矩形，由n*m个边长为1的正方形组成，连接矩形的一条对角线，求其经过矩形中多少个1*1的正方形。n <= 10^9, m <= 10^9
首先发现当n，m互质时，对角线与格点无交点。
先求n，m最大公约数g，那么线交的矩形可以分成相同的g段，此时每个矩形的对角线与格点都没有交点。那么我们只要把n/g * m/g的矩形答案*g即可。
令u=n/g，v=m/g，
此时u，v即一个小矩形的长宽
对角线线与u+1条竖线和v+1条横线相交
减去起始点相交处重合2个，那么线与整个矩形的交点数就是u+v。
即线被矩形割成u+v-1个线段（斜着看一下更清楚），
由于对角线与格点无交点，则每个线段对应于线相交的一个矩形。
即n/g * m/g的矩形的答案=u+v-1（u=n/g，v=m/g）
n*m的矩形答案即为(u+v-1)*g=(n/g+m/g-1)*g=n+m-g
T组数据，用最少个数的斐波那契数相加减表示一个数n，输出最少需使用的斐波那契数个数。举例：
10 = 5 + 5 = 3 + 7（？）
16 = 8 + 8 = 3 + 13
17 = 13 + 5 - 1对于100%的数据：n<=10^17, T <= 10
暴搜，每个数找到与它最近的斐波那契数相减即可。正确性有待证明（…………）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
template <typename T> void read(T &a) {
a = 0; char c = getchar(); T f = 1;
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) {a = a * 10 + c - '0'; c = getchar();}
a *= f;
}
long long f[100];
const long long MAXN=1e17;
int m=90; //f[1...83]<=10^17
int main(){
f[0]=0;f[1]=1;
for(int i=2;i<=m;i++){
f[i]=f[i-1]+f[i-2];
}//求第i个斐波那契数值
int t111;read(t111);
while(t111--){
long long n,ans=0;
read(n);
while(n){
int k=lower_bound(f+1,f+1+m,n)-f; //寻找f[i]>=n的最小的i
if(abs(n-f[k-1])<abs(n-f[k])){
n=abs(n-f[k-1]);
}
else n=abs(n-f[k]); //减去（加上）离n最近的一个值
//因为在加减的过程中n不断逼近0，所以无所谓符号
ans++;
}
printf("%d\n",ans);
}
return 0;
}
题意：给出两个矩形，问是否可以将一个矩形放在另一个矩形的内部（含边界）
（……）
给定n个选手，将他们分成若干只队伍。其中第i个选手要求自己所属的队伍的人数大等于a[i]人。在满足所有选手的要求的前提下，最大化队伍的总数。每个选手属于且仅属于一支队伍。
输出队伍总数的最大值以及人数最多的队伍人数
考虑贪心。
先将a[i]从大到小排个序，然后每次选择当前a[i]最大的a[i]个人分成一组，
但是这个贪心是有漏洞的，例如：4 4 4 3 1 1，
简单的贪心会将4 4 4和3 1 1分成2组，而4 4 4 3、1和1可以分成3组，
问题出在当a[i]-a[i-1]>1时，选择a[i]会比选a[i-1]多用掉名额，明显不合算，所以此时应该将a[i]并入前一组。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n); //从小到大排序，再倒着遍历
int i=n;
int s=0,ans=0,maxs=0;
while(i>0){
ans++; //队数+1
s=a[i]; //统计该组人数
i-=a[i]; //遍历到第i人，就将下标减去a[i]
while(i>0&&(a[i]-a[i-1]>1||i-a[i]<0)){ //如果a[i]-a[i-1]>1，将它并入前一组
s++;
i--;
}
maxs=max(s,maxs); //记录最多人数
}
printf("%d %d\n",ans,maxs);
return 0;
}
总的说一下今天三道题目的方法吧。吃蛋糕，求ax+by=c有多少非负整数解，只要会用扩展欧几里得算法就基本上能拿满分。01串，求用一个整数Z按照一定的程序处理后输出的01串，这样的Z有多少个，在暴力的基础上做倍增算法。没有上司的舞会，在一个有向无环图中的每一条链只能有一个结点所代表的人参加舞会，求最多能选几个结点，泉州一中好像没人会出题人的方法（如果你懂得那个方法，对不起，冒犯了），但有一个不是很正经的思路，在把每对不能同时出现在舞会的人都当成结点连上边后的图上跑一遍求二分图匹配的匈牙利算法。
