目录
成绩报告
T1说是快排，其实跟快排没有任何关系，就是单纯考了个语法。T2不会推式子，但是输出1有20分。T3不会差分约束（打拓扑排序导致的），同理输出-1得18分。T4freopen两个都是"r"，本来在结束前两分钟发现四个代码都是这个症状，已经在提交里改过了，但是在最后一分钟发现T4没加f c l o s e，加了上去，然后就没改freopen……
死亡回放
A.排座位
题目内容
题目链接
题目描述
疫情结束了，同学们终于可以返回期待已久的校园了（当然家长更是格外兴奋）。
小明作为班上的班长，提前到学校给班主任帮忙。班主任给他一个任务：把班上的同学重新排一下座位。小明心想，这对我来说太简单了，随机给每个人编号，sort 一下，任务完成。
没事做的小明感觉无比的空虚，他突然想到一句话：没有困难，创造困难也要上。所以，他给自己创造了一个小难题。
班上一共有n个同学，他给每个人编号从1~n。由于一开始给每个同学是随机编的号，所以他们构成了 的某一个全排列。虽然sort很方便而且高效，他也知道快速排序是怎么执行的（你们知道吗），但是他想知道如果只通过两个元素（不一定相邻）交换的方式，让这个全排列变成升序序列，最小的交换次数是多少？
他思考了一下，感觉这个问题挺有意思，所以让你也来解决一下。
输入格式
第一行一个正整数n，表示学生总数。
第二行n个正整数，从1~n，表示他给n个同学随机编号的结果。
输出格式
一行一个整数，表示最小的交换次数。
数据范围与提示
\(1<=n<=1,000,000\)
思路
史诗级题目误导，与快排和逆序对没有一点关系，因为实在记不清不想打逆序对所以很快就想到了暴力的解法。本题的数据范围也是相当炸裂，但是暴力O(n)拿下。
另一个思路参见DanhengYinyue
代码
#include<bits/stdc++.h>
using namespace std;
long long a,b[5000005],pl[5000005],ans;
int main()
{
freopen("seat.in","r",stdin);
freopen("seat.out","w",stdout);
scanf("%lld",&a);
for(register int i=1;i<=a;i++)
{
scanf("%lld",&b[i]);
pl[b[i]]=i;//存某个数的初始位置。
}
for(register int i=1;i<=a;i++)
{
while(pl[b[i]]!=b[i])//交换一次
{
int j=pl[b[i]];
pl[b[i]]=pl[j];
pl[j]=j;
ans++;
}
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
B.梦中的学校
题目内容
题目链接
题目描述
疫情马上要结束了，开学的日子就要来临了。但是小明已经在家里呆习惯了，因此他感到非常的紧张。
这天晚上，小明做了一个奇怪的梦。他梦到自己走到了一个奇怪的学校，这个学校有唯一的一个入口。学校由若干教室组成，每个教室被粉刷了若干种颜色的一种，教室之间有连廊连接。如果我们把连廊看做边，把教室当做结点的话，那么这个学校就变成了一个有根树。每个结点的子树之间是有序的。
小明感觉有点害怕了，他不管直接进去。这时梦境中突然多了一个小明的分身，叫小明明，所以他让小明明帮忙去探探路。
小明明从学校的入口进去，之后对整个学校进行深度优先遍历。小明明每次进入一间教室（包括返回），都会记录下这间教室的颜色，最后从入口出来告诉小明具体情况。
每间教室小明明至少都会去一次，并且每个连廊他也恰好经过两次（双向个一次）。最后小明明可以得到一个颜色的序列。但是小明明把序列交给小明之后，他发现这个序列并不能唯一确定整个学校的结构。现在他想请你帮忙计算一下，对弈一个给定的颜色序列，会对应多少中可能的学校结构。由于结果可能很大，你只需要输出对\(10^9\)取模的结果。
输入格式
一个由大写字母组成的字符串S，表示小明明给小明的颜色序列。
输出格式
一个整数表示答案。
思路
最初看到这道题想起了二叉树的遍历，然后看到取模，就想到了数学，而且huge在考试以前说了要考扩展卢卡斯，这四道题也就这一个和它沾点边，所以跑偏了。不过数据是真水，输出1骗20分。这题的解法其实就是区间dp，即使打记搜也是类似的思路，递推方程我没推出来，所以打的还是记搜。因为小明的替身走的是来回，所以只有开头和结尾相等的串才会产生合法的情况。单个字符当然只有一种情况。合法情况下的三个字符也是只有一种情况，所以循环从lt+2开始，枚举可以作为返回点的字符，即i处回到了起点，两边不同情况的搭配数应相乘，然后就得出了状态转移方程：
一定要记得多模几遍！！！一定要记得开long long！！！
代码
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000000;
long long a,dp[2002][2002],b,ans;
char c[10000001];
inline long long dfs_pro(long long lt,long long rt)
{
if(dp[lt][rt]!=-1)//记忆的部分
{
return dp[lt][rt];
}
if(lt>rt)//非法情况
{
return 0;
}
if(lt==rt)//单个字符情况特判
{
return 1;
}
dp[lt][rt]=0;//先置零
if(c[lt]==c[rt])
{
for(register long long i=lt+2;i<=rt;i++)
{
dp[lt][rt]+=(dfs_pro(lt+1,i-1)%mod)*(dfs_pro(i,rt)%mod)%mod;//多模几遍总不会有坏处
dp[lt][rt]%=mod;
}
}
return dp[lt][rt];
}
int main()
{
freopen("school.in","r",stdin);
freopen("school.out","w",stdout);
scanf("%s",c);
b=strlen(c);
memset(dp,-1,sizeof(dp));
ans=dfs_pro(0,b-1);//注意char数组是从0开始
printf("%lld",ans%mod);
fclose(stdin);
fclose(stdout);
return 0;
}
C.激突冲击
题目内容
题目链接
题目描述
布基纳法索空军最近在瓦加杜古上空18000米处发现了一艘残破的航天母舰，在经过精细的搜查之后，布基纳法索空军发现这架空母上的大多数武器装置仍处于工作状态！如果让其启动，那么整个国家甚至周边地区都有可能遭受灭顶之灾！所幸整架空母之上的唯一一位幸存者――一位自称HS的神奇生物在见到布基纳法索空军之后告诉空军们关闭武器系统的方式――把船拆了。可是由于HS的身体构造过于神奇，被布基纳法索国家医院征用去做活体解剖了，空军战士们只能自行拆船。
研究发现，空母由N个子舱室和M个活塞组成，只要按照正确的方式推动活塞，舱室就会自动解体。但是要推动活塞需要在活塞相连的两个舱室分别施加一定的力（别问我为什么不能只推一个）并且两个力之间有一定约束关系。综上，布基纳法索空军决定在每个舱室上放一定量的【数据删除】，用冲击力推动活塞。
下面给出舱室间推力关系(T,A,B)
T=1代表A舱与B舱推力相等
T=2代表A舱推力小于B舱
T=3代表A舱推力不小于B舱
T=4代表A舱推力大于B舱
T=5代表A舱推力不大于B舱
由于【数据删除】用量和所产生推力成正比，因此上述关系可视为在各舱室放置【数据删除】数量的关系
为了尽可能的减少【数据删除】的用量，你需要求出整个爆破过程【数据删除】的消耗总量（其中最少的舱室放置1单位的【数据删除】，各舱室【数据删除】量为整单位）
如果不可能完成任务，输出-1
输入格式
第一行两个正整数N,M。
接下来M行每行描述一组关系(T,A,B)。
输出格式
一个整数，表示最小【数据删除】用量或-1。
数据范围与提示
\(N,M<=10^5\)
思路
最典型的差分约束题，其实就是糖果。他们打差分时我在打拓扑排序，所以不会打。但是考前看了一眼，所以知道它是差分约束。如果不知道，有可能赛时打Tarjan+拓扑排序就出来了。这题直接打SPFA会被卡，最后还是我以为最暴力的解法成了正解。通过关系连边建图，注意建超级原点，然后跑Tarjan，从0开始。缩点时判非法情况，然后拓扑排序找每个点的最小值，最后相加即可。
代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long h,to,quan,frm;
}way[5000005],now[5000005];
long long a,b,c,g,f[50000005],cnt,num,l,t[5000005];
bool e[5000005],in[5000005];
long long out[5000005];
long long d[5000005],ans,dfs[5000005],low[5000005],be[5000005],ng[5000005];
stack<int>use;
inline void ndin(long long x,long long y,long long z)//第二个图的输入函数
{
g++;
way[g].quan=z;
way[g].to=y;
way[g].h=f[x];
way[g].frm=x;
f[x]=g;
}
inline void ndscan(int x,int y,int z)//第一个图的输入函数
{
l++;
now[l].quan=z;
now[l].to=y;
now[l].h=t[x];
now[l].frm=x;
t[x]=l;
}
inline void pit()//缩点函数，缩点的同时可以判非法环
{
for(int i=1;i<=l;i++)
{
if(be[now[i].frm]!=be[now[i].to])
{
ndin(be[now[i].frm],be[now[i].to],now[i].quan);
out[be[now[i].to]]++;
continue;
}
if(be[now[i].frm]==be[now[i].to]&&now[i].quan==1)
{
puts("-1");
exit(0);
}
}
}
void tarjan(int x)//经典塔尖，无话可说
{
num++;
dfs[x]=num;
low[x]=num;
use.push(x);
in[x]=1;
for(int i=t[x];i>0;i=now[i].h)
{
if(dfs[now[i].to]==0)
{
tarjan(now[i].to);
low[x]=min(low[x],low[now[i].to]);
continue;
}
if(in[now[i].to]==1)
{
low[x]=min(low[x],dfs[now[i].to]);
continue;
}
}
if(low[x]==dfs[x])
{
int y;
cnt++;
do
{
y=use.top();
use.pop();
be[y]=cnt;
ng[cnt]++;
in[y]=0;
}
while(y!=x);
}
}
void tpst()//拓扑排序
{
queue<int>tp;
for(int i=1;i<=cnt;i++)
{
if(out[i]==0)
{
tp.push(i);
}
}
while(tp.empty()==false)
{
int st=tp.front();
tp.pop();
for(int i=f[st];i>0;i=way[i].h)
{
out[way[i].to]--;
d[way[i].to]=max(d[way[i].to],d[st]+way[i].quan);
if(out[way[i].to]==0)
{
ans+=d[way[i].to]*ng[way[i].to];
tp.push(way[i].to);
}
}
}
}
int main()
{
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
scanf("%lld%lld",&a,&b);
for(register long long i=1;i<=a;i++)//超级原点
{
ndscan(0,i,1);
}
for(register long long i=1;i<=b;i++)//输入
{
long long u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
if(u==1)
{
ndscan(v,w,0);
ndscan(w,v,0);
}
if(u==2)
{
if(v==w)
{
puts("-1");
exit(0);
}
ndscan(v,w,1);
}
if(u==3)
{
ndscan(w,v,0);
}
if(u==4)
{
if(v==w)
{
puts("-1");
exit(0);
}
ndscan(w,v,1);
}
if(u==5)
{
ndscan(v,w,0);
}
}
for(int i=0;i<=a;i++)//经典防丛林
{
if(dfs[i]==0)
{
tarjan(i);
}
}
pit();
tpst();
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
D.奖学金
题目内容
题目链接
题目描述
猪仙发现人类可以上很多大学，而猪们却没有大学可上。为了解决这个问题，于是他创立了一所大学，取名为猪仙大学。
为了选拔合适的学生入学，他发明了一种学术能力测试（简称CSTA），这种测试的分数异常精确，每头猪的成绩可以用1到2,000,000,000之间的一个整数表示。
猪仙大学的学费很贵（猪仙比较黑），很多猪都负担不起，他们需要申请一些奖学金（\(1<=奖学金<=10000\)）。可是政府并没有为猪准备奖学金，于是所有的预算都必须要从学校自身有限的基金中间扣除（设基金总额为F,$0<=F<=2,000,000,000）。
更槽的事，猪仙大学的只有N(\(1<=N<+19999\))间教室，N是一个奇数，而一共有C(\(N<+C<+100,000\))头猪申请入学，为了让最多的猪接受教育，猪仙打算接受N头猪的申请，而且她还想让这些猪CSTA成绩的中位数尽可能地高。
所谓中位数，就是在一堆数字在排序后处在最中间的那个数字，比如{3,8,9,7,5}的中位数就是7。
给定每头猪的CSTA成绩和打算申请的奖学金数目，以及可以资助的基金总数，确定猪仙接受哪些猪的申请才可以使成绩的中位数达到最大。
输入格式
第一行：三个用空格分开的整数：N,C和F。
第二行到C+1行：每行有两个用空格分开的整数。第一个数是这头猪的CSTA成绩，第二个数是这头猪想申请的奖学金。
输出格式
第一行：一个整数，表示猪仙可以得到的最大中位数，如果现有基金不够资助N头猪，则输出-1。
思路
数据范围吓人，但也是道暴力过了的。一开始想背包dp，但是无法保证有n人。然后想返回贪心，应该可以实现，但是我菜，不会，赛时打的二分，能过赛时的数据。但是其实这道题是不能用二分打的，原因就是答案不具有单调性。
卡二分的数据
3 9 15
1 1
2 3
3 3
4 4
5 5
6 10
7 10
8 8
9 5
从这里就可以看出来我为什么被卡掉。先二分找成绩5，不行，但其实5上面还有更优的情况，我们找不到。所以我用二分改暴力，成绩从高往低找，就可以过了。check函数是这样的：先看成绩位置可不可以是中位数，即排除边界情况。然后按钱数找，记录小于soe[x]和大于soe[x]的数目不超过a,另外还要特判自己。如果钱数大于了c，就是false。
代码
#include<bits/stdc++.h>
using namespace std;
struct node1
{
long long mny,soe;
bool operator<(const node1 &A)const
{
if(mny==A.mny)
{
return soe>A.soe;
}
return mny<A.mny;
}
}pig1[200002];//按钱数排
struct node2
{
long long mny,soe;
bool operator<(const node2 &A)const
{
if(soe==A.soe)
{
return mny<A.mny;
}
return soe<A.soe;
}
}pig2[200002];//按分数排
long long a,b,c;
inline bool check(long long x)//曾经二分用的check
{
if(x<=a/2||x>b-a/2)//判边界位置
{
return false;
}
long long num1=0,num2=0,sm=0;
bool deng=false;
for(register long long i=1;i<=b;i++)
{
if(pig1[i].soe==pig2[x].soe&&deng==false)//判自己，只判一次
{
sm+=pig1[i].mny;
if(sm>c)
{
return false;
}
deng=false;
continue;
}//后面分别判大于和小于
if(pig1[i].soe<=pig2[x].soe&&num1<a/2)
{
num1++;
sm+=pig1[i].mny;
if(sm>c)
{
return false;
}
continue;
}
if(pig1[i].soe>=pig2[x].soe&&num2<a/2)
{
num2++;
sm+=pig1[i].mny;
if(sm>c)
{
return false;
}
continue;
}
}
return true;
}
int main()
{
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
scanf("%lld%lld%lld",&a,&b,&c);
for(register long long i=1;i<=b;i++)
{
scanf("%lld%lld",&pig1[i].soe,&pig1[i].mny);
pig2[i].soe=pig1[i].soe;
pig2[i].mny=pig1[i].mny;
}//接下来分别sort一遍
sort(pig1+1,pig1+1+b);
sort(pig2+1,pig2+1+b);
for(int i=b;i>0;i--)//从大到小找
{
if(check(i)==true)
{
printf("%lld",pig2[i].soe);
fclose(stdin);
fclose(stdout);
return 0;
}
}
puts("-1");//找不到就是错了
fclose(stdin);
fclose(stdout);
return 0;
}
一个小彩蛋
现在知道什么是【数据删除】了吧。