2018.4.10题目总结

##[[HNOI2002]公交车路线](https://www.luogu.org/problemnew/show/P2233) 在长沙城新建的环城公路上一共有8个公交站，分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站A到公交站D，你就至少需要换3次车。 Tiger的方向感极其糟糕，我们知道从公交站A到公交E只需要换4次车就可以到达，可是tiger却总共换了n次车，注意tiger一旦到达公交站E，他不会愚蠢到再去换车。现在希望你计算一下tiger有多少种可能的乘车方案。  输入文件当中仅有一个正整数n(4<=n<=10000000)，表示tiger从公交车站A到公交车站E共换了n次车 输出文件仅有一个正整数，由于方案数很大，请输出方案数除以 1000后的余数。 解法： 矩阵乘法 有一个定理是，在一个矩阵中，如果把原始矩阵中可以通行的边的权值赋为1，然后再将其K次方，假设a[i][j]=n,那么a[i][j]表示的意思就是：从i到j长度为K的路径有n条。 所以用1-8表示A-H这8个车站，将相邻的车站连边，那么用上述定理即可求出。此题需要额外注意的是Tiger到达E后就不会再行走，所以路程中间不能经过E。 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=9,P=1e3; struct ju{ ll a[N][N]; void clear(){ memset(a,0,sizeof(a)); } void init(){ for(int i = 0;i<=N;i++){ a[i][i]=1; } } }A; ju operator * (ju a,ju b){ ju c; c.clear(); for(int i = 1;i<=8;i++){ for(int j = 1;j<=8;j++){ for(int k = 1;k<=8;k++){ if(k!=5){ c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%P)%P; } } } } return c; } ju qpow(ju a,ll b){ ju ret; ret.clear(); ret.init(); while(b){ if(b&1) ret=ret*a; b>>=1; a=a*a; } return ret; } ll n; int main(){ cin>>n; A.clear(); for(int i = 2;i<=7;i++){ A.a[i][i-1]=A.a[i][i+1]=1; A.a[i-1][i]=A.a[i+1][i]=1; } A.a[8][7]=A.a[8][1]=A.a[1][8]=A.a[1][2]=1; ju Ans=qpow(A,n); cout<<Ans.a[1][5]; return 0; } ``` ------------ ##[[HNOI2008]越狱](https://www.luogu.org/problemnew/show/P3197) 监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱 输入两个整数M，N.1<=M<=10^8,1<=N<=10^12 可能越狱的状态数，模100003取余 解法： 快速幂，容斥原理 如果直接考虑可能越狱不方便的话，可以考虑使用容斥原理。 总共可能的宗教信仰状态有m^n，接下来考虑不会越狱的情况，第一间屋子的人可以有m种信仰，接下来(n-1)间屋子里的人，每一个屋子只需要与前一个屋子中的人宗教信仰不同即可，所以每一个人可以信仰与前一个屋子的人不同的(m-1)种宗教，那么不会越狱的情况就总共有m(m-1)^(n-1)种。 所以最后答案就是m^n-m(m-1)^(n-1)。 需要注意一点最后先+P再%P防止出现负数。 ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int P=1e5+3; ll n,m,sum; inline ll qpow(ll a,ll b){ ll ret=1; while(b){ if(b&1) ret=ret*a%P; b>>=1; a=a*a%P; } return ret; } int main(){ scanf("%lld%lld",&m,&n); sum=qpow(m,n); ll ans=qpow(m-1,n-1); ans=ans*m%P; printf("%lld",(sum-ans+P)%P); return 0; } ``` ------------ ##[[HNOI2003]消防局的设立](https://www.luogu.org/problemnew/show/P2279) 2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。 由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。 你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。 输入文件的第一行为n （n<=1000），表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]<i。 输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。 解法： 贪心，DFS 先DFS处理出每个节点的深度 考虑当前深度最大的子节点，我们想设立消防站能够到达这个节点，那么贪心地在这个节点的父亲的父亲节点设立一个消防站，这样肯定是最优的（~~大概思考然后反证一下~~）。 ```cpp #include<bits/stdc++.h> using namespace std; const int N=1001; int head[N],cnt,n,fa[N],ans,deep[N]; bool vis[N]; struct tu{ int ne,to; }e[2*N]; struct shu{ int id,deep; }s[N]; bool cmp(shu a,shu b){ return a.deep>b.deep; } void add(int u,int v){ cnt++; e[cnt].to=v; e[cnt].ne=head[u]; head[u]=cnt; cnt++; e[cnt].to=u; e[cnt].ne=head[v]; head[v]=cnt; } void dfs(int u){ for(int j = head[u];j;j=e[j].ne){ int v=e[j].to; if(!deep[v]) deep[v]=deep[u]+1,fa[v]=u,dfs(v); } return; } void solve(int x,int f,int w) { if(!w) return ; for(int i = head[x];i;i=e[i].ne){ int now=e[i].to; if(now!=f){ vis[now] = true; solve(now,x,w-1); } } } int main(){ scanf("%d",&n); for(int i = 2;i<=n;i++){ int a; scanf("%d",&a); add(a,i); } dfs(1); for(int i = 1;i<=n;i++){ s[i].id=i; s[i].deep=deep[i]; } sort(s+1,s+n+1,cmp); fa[1]=1; for(int i = 1;i<=n;i++){ int g=s[i].id; if(!vis[g]){ int k = fa[fa[g]]; vis[k]=true; solve(k,0,2); ans++; } } printf("%d\n",ans); return 0; } ``` ------------ ##[[ZJOI2008]泡泡堂BNB](https://www.lydsy.com/JudgeOnline/problem.php?id=1034) 第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场得1分输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。作为浙江队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，浙江队最终分别能得到多少分。 输入的第一行为一个整数n，表示每支代表队的人数。接下来n行，每行一个整数，描述了n位浙江队的选手的 实力值。接下来n行，每行一个整数，描述了你的对手的n位选手的实力值。 20％的数据中，1<=n<=10； 40％的数 据中，1<=n<=100； 60％的数据中，1<=n<=1000； 100％的数据中，1<=n<=100000，且所有选手的实力值在0到100 00000之间。 包括两个用空格隔开的整数，分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的 空白字符。 解法： 贪心 类似于田忌赛马的思想，我们将浙江队存为a[l1]~a[r1]，其他队存为b[l2]~b[r2],当然l1<=r1并且l2<=r2，分为以下三种情况 Case 1：我们当前最坏的马比对面当前最坏的马强，这时我们就让双方当前最坏的马比赛，我们胜利，得两分。 Case 2：我们当前最好的马比对面当前最好的马强，同Case 1，我们让双方当前最好的马比赛，我们胜利，得两分。 Case 3：如果以上两种情况都不满足，回想一下田忌赛马的故事，这时候我们就让我们当前最坏的马和对面当前最好的马比赛，达到消耗对面精锐力量的目的，注意的是比赛规则允许平局，所以需要判断我方当前最坏的马和对面当前最好的马是否会平局，如果平局我们就能的得一分，如果不能平局我们就得0分。 根据以上三种策略，我们可以求得我方的最大得分。 现在考虑我方的最小得分，思考一下双方所有比赛后的总得分，我们可以发现，每一局比赛双方总得分都是2分（要么我得两分，要么对面两分，要么一人一分），所以所有比赛结束后双方总得分是2*n分。 那么要求我方最小得分，只需要求出对方最大得分，再用2*n减去对方最大得分即可。 ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+3; int a[N],b[N],n,ans; int solve(int a[],int b[]){ int ans=0; int l1=1,l2=1,r1=n,r2=n; while(l1<=r1&&l2<=r2){ if(a[l1]>b[l2]) ans+=2,l1++,l2++; else if(a[r1]>b[r2]) ans+=2,r1--,r2--; else ans+=(a[l1]==b[r2]),l1++,r2--; } return ans; } int main(){ scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); for(int i = 1;i<=n;i++) scanf("%d",&b[i]); sort(a+1,a+n+1); sort(b+1,b+n+1); printf("%d %d",solve(a,b),2*n-solve(b,a)); return 0; } ``` ------------ ## [[JSOI2008]最大数maxnumber](https://www.lydsy.com/JudgeOnline/problem.php?id=1012) 现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加 上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取 模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个 数。 第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来 M行，查询操作或者插入操作。 对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。 解法： 单调队列 ~~这题正解线段树~~ ~~但是我们可以拿单调队列直接做，维护最大值即可~~ ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int m,d,a[200005],p[200005],cnt,l,n,ans; char s; int main(){ scanf("%d%d",&m,&d); while(m--){ scanf("%s",&s); if(s=='Q'){ scanf("%d",&l); ans=p[cnt-l+1]; printf("%d\n",ans); } if(s=='A'){ scanf("%d",&n); a[++cnt]=(ans+n)%d; for(int i = cnt;i>0;i--){ if(p[i]<a[cnt]) p[i]=a[cnt]; else break; } } } return 0; } ``` ------------ ##[[SCOI2005]扫雷](https://www.luogu.org/problemnew/show/P2327)  输入格式： 第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000） 输出格式： 一个数，即第一列中雷的摆放方案数。 解法： 递推，第一个格子有两种可能，即有地雷或没有地雷，然后根据当前格子和上一个格子可以推出下一个格子。最后检验是否成立，检验的方法就是看我们递推出来的第n+1个格子有没有地雷，如果有当然是不成立的。 ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=1e4+3; int n,a[N],f[N],ans; bool check(){ for(int i = 2;i<=n;i++){ f[i+1]=a[i]-f[i]-f[i-1]; } if(f[n+1]) return false; return true; } int main(){ scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); for(int i = 0;i<=a[1];i++){ f[1]=i; f[2]=a[1]-f[1]; if(check()) ans++; } printf("%d\n",ans); return 0; } ```