cf一如既往挺丧
看丧题点我！
【A】分数
Petya是数学迷，特别是有关于分数的数学。
最近他学了所谓一个分数被叫做“真分数”当且仅当其分子小于分母，而一个分数被叫做“最简分数”当且仅当其分子分母互质。
在闲暇时间，Petya在用计算器研究：如何把最简真分数转换为小数等问题。有一天他不小心把除号(÷)按成了加号(+)，导致他得到了分子与分母的和。
Petya想要得到他原来的分数，但他很快发现这不是唯一的。所以现在他想要知道最大的最简真分数使得其分子与分母的和为n。
输入
一个正整数，n(3<=n<=1000)。
输出
两个数，最大的最简真分数的分子与分母。
样例输入1
3
样例输出1
1 2
样例输入2
6
样例输出2
1 5
题解
很简单的一题。枚举分子算分母，判断分子分母的gcd是否为1。
1 #include<cstdio>
2 int gcd(int x,int y){return y?gcd(y,x%y):x;}
3 int n,ans;
4 int main(){
5 scanf("%d",&n);
6 for(int i=1;(i<<1)<n;++i) if(gcd(i,n-i)==1) ans=i;
7 printf("%d %d\n",ans,n-ans);
8 return 0;
9 }
【B】Maxim买公寓
Maxim要买公寓。Maxim要住在首府的线条大道的一栋房子里。这栋房子有n个单间，排列在一条线上。有些单间有人住，而有些待售。
Maxim喜欢去拜访他的邻居，所以他觉得，如果这间公寓待售，且相邻的公寓里有人住，这间公寓就是好的。
Maxim知道这n间公寓中，有k个是有人住的。他想知道好的公寓的最大和最小数量。
输入
两个数，n,k。(1<=n<=10^9, 0<=k<=n)
输出
两个数，好公寓的最大和最小数量。
题解
很水啊。分四类讨论：
① k=0 : 0 0。
② 0<3k<=n : 1 2k。
③ n<3k<3n : 1 n-k。
④ k=n : 0 0。
1 #include<cstdio>
2 int n,k;
3 int main(){
4 scanf("%d%d",&n,&k);
5 if(k==n||k==0){puts("0 0");return 0;}
6 printf("1 ");
7 if(k*3ll<=n) printf("%d",2*k);
8 else printf("%d",n-k);
9 return 0;
10 }
【C】计划
丧
【D】评委会议
有点难打，不会丧。
天府之国很快要举行大都会运动会，这意味着所有的运动会评委必须来到首府（首都）举行一次会议。
有n+1个城市编号从0~n，0号城市是首府，评委们的见面地点。而编号1~n的城市中，每个城市恰好有一个评委。会议要讨论的内容十分复杂，要持续k天，每天每个评委都必须在首府以便于解决问题。
你知道了天府之国的航班表（共m趟航班）（评委们十分高冷，只愿意搭飞机出行）。天府之国的所有航班要不然是从首府起飞，要不然是在首府落地，而且没有夜间飞行，这意味着航班只会飞一天，旅客登机和下飞机是在同一天。在评委到达和离开首府的当天，他无法参与会议。
把所有人聚集到首府是很难的，而要计算其最小费用更是难上加难。虽然如此，你还是要求出最便宜的一种方法，让所有的评委来到首府，开k天的会再安全离开首府回到自己的家乡。
输入
第一行，三个正整数，n,m,k。
接下来m行，每行三个数，di,fi,ti,ci，分别表示第i趟航班的时间，出发城市，到达城市以及费用。
输出
最小费用，如果无法做到，输出-1。
样例输入
2 6 5
1 1 0 5000
3 2 0 5500
2 2 0 6000
15 0 2 9000
9 0 1 7000
8 0 2 6500
样例输出
24500
题解
①航班按时间排序
②求出两个航班Min,Max，满足1~Min的航班中，所有评委可以到达首府，Max~m的航班中，所有评委可以离开首府。
③计算Min+1~Max-1中的最小费用。
④双指针扫描
1 #include<cstdio>
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #define F(i,a,b) for(int i=a;i<=b;++i)
6 #define dF(i,a,b) for(int i=a;i>=b;--i)
7 #define F2(i,a,b) for(int i=a;i<b;++i)
8 using namespace std;
9 int n,m,k,d[100001],f[100001],t[100001],c[100001],I[100001];
10 inline int Min(int x,int y){return x<y?x:y;}
11 inline long long Min(long long x,long long y){return x<y?x:y;}
12 inline bool cmp(int p1,int p2){return d[p1]<d[p2];}
13 int Dep[100001],Depnum,Arr[100001],Arrnum;
14 int Minmeet=-1,Maxmeet=-1,Mini,Maxi;
15 int CityD[100001],CityA[100001];
16 long long MinDC[100001],MinAC[100001],Ans=9999999999999999ll;
17 void init(){
18 scanf("%d%d%d",&n,&m,&k);
19 F(i,1,m) scanf("%d%d%d%d",d+i,f+i,t+i,c+i),I[i]=i;
20 sort(I+1,I+m+1,cmp);
21 // puts("====");
22 // F(i,1,m) printf("%d %d %d %d\n",d[I[i]],f[I[i]],t[I[i]],c[I[i]]);
23 // puts("====");
24 }
25 int main(){
26 init();
27 F(i,1,m){
28 if(t[I[i]]==0){
29 CityD[f[I[i]]]=Min(CityD[f[I[i]]],c[I[i]]);
30 if(!Dep[f[I[i]]])
31 CityD[f[I[i]]]=c[I[i]], Dep[f[I[i]]]=1, ++Depnum;
32 }
33 if(Depnum==n) {Minmeet=d[I[i]]+1; Mini=i; break;}
34 }
35 dF(i,m,1){
36 if(f[I[i]]==0){
37 CityA[t[I[i]]]=Min(CityA[t[I[i]]],c[I[i]]);
38 if(!Arr[t[I[i]]])
39 CityA[t[I[i]]]=c[I[i]], Arr[t[I[i]]]=1, ++Arrnum;
40 }
41 if(Arrnum==n) {Maxmeet=d[I[i]]-1; Maxi=i; break;}
42 }
43 // printf("Meeting: %d - %d\n",Minmeet,Maxmeet);
44 if(Minmeet==-1||Maxmeet==-1||Maxmeet-Minmeet+1<k) {puts("-1"); return 0;}
45 F(i,1,n) MinDC[Mini]+=CityD[i];
46 F(i,1,n) MinAC[Maxi]+=CityA[i];
47 F(i,Mini+1,m){
48 MinDC[i]=MinDC[i-1];
49 if(t[I[i]]==0)
50 if(CityD[f[I[i]]]>c[I[i]]) MinDC[i]-=CityD[f[I[i]]]-c[I[i]], CityD[f[I[i]]]=c[I[i]];
51 }
52 dF(i,Maxi-1,1){
53 MinAC[i]=MinAC[i+1];
54 if(f[I[i]]==0)
55 if(CityA[t[I[i]]]>c[I[i]]) MinAC[i]-=CityA[t[I[i]]]-c[I[i]], CityA[t[I[i]]]=c[I[i]];
56 }
57 // F(i,Mini,m) printf("%I64d ",MinDC[i]); puts("");
58 // F(i,1,Maxi) printf("%I64d ",MinAC[i]); puts("");
59 for(int i=Mini,j=Mini;i<=Maxi&&j<=Maxi;++i){
60 while(j<=Maxi&&d[I[j]]-d[I[i]]-1<k) ++j;
61 if(j>Maxi) break;
62 Ans=Min(Ans,MinDC[i]+MinAC[j]);
63 }
64 cout<<Ans;
65 return 0;
66 }
【E】烦闷
丧，目测神秘数结