伟大的IOI的博客

思路。找规律题。 发现数列每 10 个一循环，所以我们只需要掏出电脑上自带的计算器算一下就能知道这个数是 2429042904288。 输出即可。 AC 代码。12345public class Main { public static void main(String[] args) { System.out.println("2429042904288"); }}

由于拓扑排序连边规则是对于两个点 $a_i,a_j$，如果 $i<j$，那么将 $a_i$ 连向 $a_j$。 因为数据很小，所以我们用 next_permutation 求出第 $k$ 个排列，再将每个数在此排列中的位置存起来，按照上面的规则连边即可。 123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;int n,m,k,a[10005],b[10005];int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++){ a[i]=i; } for(int i=1;i<=k-1;i++){ next_permutation(a+1,a+n+1); } for(int i=1;i<=n;i++){ b[a[i]]=i; } for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; cout<<(b[u ...

CF1982B 题解思路：我们直接模拟的话肯定会超时，所以考虑优化。 我们注意到每次操作 $x$ 才加 1，对于计算机来说有点太屈才了。 所以我们考虑在一次操作内将 $x$ 加到能整除 $y$，并在 $x$ 等于 1 时退出循环这样就能省去很多时间。 注意：由于我们在 $x$ 等于 1 时就退出了循环，所以要在循环外面检查一下是否有剩余。 代码：123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>#define int long longusing namespace std;int x,y,k;int K;signed main(){ cin>>K; while(K--){ cin>>x>>y>>k; while(k>0&&x!=1){ if(k>=y-(x%y)){ k-=y-(x%y); x+=y-(x%y); while(x%y==0)x/=y; } el ...

思路：贪心+模拟。我们将当前的指令分给使用此指令后可以缩短两者之间距离的那个。具体来说： 如果指令为 N，就将它分给 y 坐标较小的。 如果指令为 S，就将它分给 y 坐标较大的。 如果指令为 E，就将它分给 x 坐标较小的。 如果指令为 W，就将它分给 x 坐标较大的。 有个坑点，就是每个机器人都必须移动。

提供一个不一样的做法。 思路：众所周知，这题每合并一次就排序一次会超时，所以我们不排序不进行完全的排序。 我们可以在第一次合并前先排一次，这样每次合并后只需对合并后的数进行冒泡，遇到比它小的就交换，遇到比它大的就停止，因为后面的数已经有序了。 代码：12345678910111213141516171819202122232425#include<bits/stdc++.h>using namespace std;const int N=20000+5;int n,a[N],ans;int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); for(int i=1;i<=n-1;i++){ ans+=a[i]+a[i+1]; int c; c=a[i]+a[i+1]; a[i+1]=c; for(int j=i+1;j<=n-1;j++){ if(a[j]>a[j+1]){ swap(a[j+1],a[j]); } ...

CF1989C Two Movies 题解思路：考虑贪心。 这题分两种情况： $a_i\ne b_i$，这时选最大的加为最优。 $a_i= b_i$，用一个数组先存起来，最后再将小于零的加给大的，大于零的加给小的，使小的尽量大。 代码：1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using namespace std;int t,n,a[11451419],b[11451419],c[11451419],aa,bb,ii;int maxn,minn;int main(){ cin>>t; while(t--){ cin>>n; bb=aa=0; ii=0; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; } for(int i=1;i<=n; ...

题意：构造一个字符串 $c$，使 $a$ 为 $c$ 的字串且 $b$ 为 $c$ 的子序列，求 $c$ 的最小长度。 思路：设 $a$ 的长度为 $lena$，$b$ 的长度为 $lenb$，$a$ 与 $b$ 的最大公共子序列长度为 $s$，因为 $c$ 中一定包含 $a$ 跟 $b$ 中的所有字符，所以我们可以知道 $c$ 的最小长度为 $lena+lenb-s$。 代码：1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;int t,maxn=-1;string s,ss;int main(){ cin>>t; while(t--){ cin>>s>>ss; int lena,lenb; lena=s.size(); lenb=ss.size(); maxn=-1; for(int i=0;i<lenb;i++){ int n=i,len=0; for(int j=0;j<lena ...

前置知识： to_string() 函数 将 Dev-C++ 改为 c++14 思路：为什么要改为 c++14 呢？因为 to_string() 这个函数到 c++14 才有，而 DEV 默认是 c++11。 我们枚举这个区间，将其中的每个数用 to_string() 变为字符串，这样就可以枚举它的每一位，方便判断。 若字符串的长度为 $s$，则枚举位数的循环只需循环 $\left \lfloor \frac{s}{2} \right \rfloor$ 次即可。 若此字符串为 $w$，则 $wi$ 对应的为 $w{s-i-1}$。 按照这个将相等的组数记下来，如果它是回文数的话，那么相等的组数应为 $\left \lfloor \frac{s}{2} \right \rfloor$。 判断一下即可。 注意：数据范围为 $1 \le S \le E \le 10^{18},E-S+1\le 10^5$，需要开 long long。 AC 代码：12345678910111213141516171819202122#include<bits/stdc++.h>using ...

思路：其实就是将每个数分解质因数，只不过需要加亿点点优化： 在找到一个质因数后，要用一个循环将这个因数除干净，这样下次遇到时就不会再统计一遍，达到去重的目的。 先将 $2$ 这个特殊的质数除掉，后面从 $3$ 开始除，每次加 $2$，这样能省下挺多时间。 AC 代码：12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>using namespace std;bool is_prime(int n) { int i; if(n<2)return 0; for(i=2; i*i<=n; i++) { if(n%i==0) { return 0; break; } } return 1;}//判断是否为质数int main() { int n,k,c=0; cin>>k; for(int i=1; i<=k; i++) { cin>>n; if(is_prime(n)) ...

思路：要先搞懂实际能坐的有几个座位。稍微用脑子想一想即可知道一共有 $\left \lfloor \frac{n+1}{2} \right \rfloor$ 个座位。剩下的就好办了。 先将他们的快乐值排序，然后在有限的空间里将比较大的且大于零的加进来即可。 注意：很喜欢 OIer 们的一句话：十年 OI 一场空，不开 long long 见祖宗。 AC 代码：12345678910111213141516171819#include<bits/stdc++.h>using namespace std;long long n;long long a[11451419],c;int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); for(int i=n;i>n/2;i--){ if(a[i]<=0){ break; } c+=a[i]; } cout<<c; return 0;}

思路：一道贪心题。只需要判断当日用第一种票花钱多还是第二种票花钱多，再将花钱少的哪一种加入到总钱数中即可。 AC 代码：1234567891011121314151617#include<bits/stdc++.h>using namespace std;int n,x,y,a,c;int main(){ cin>>n>>x>>y; for(int i=1;i<=n;i++){ cin>>a; if(a*x>=y){ c+=y; } else{ c+=a*x; } } cout<<c; return 0;}

原题传送门 思路这题直接模拟过即可，根本不需要什么线段树。 仔细看数据范围，发现仅仅是$1\le n\le 5000,0\le l\le r\le 10^{6} $。 于是暴力也能过。 储存每个人的时间建议用结构体，里面放开始时间和结束时间。 因为范围特别小，所以用一个数组来储存这一秒有没有人挤奶。 然后再将每一段挤奶时间的秒数放进一个数组里排一下序，输出最大的即可。 最短空闲时间如法炮制即可。 要注意求每一段挤奶时间的秒数时要从最开始挤奶的时间枚举到最后挤奶的时间，否则会爆炸。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<bits/stdc++.h>using namespace std;int n,minn=1145141919,ll=-1,maxn=-1,rr=1,s[11451419],c[11451419],cc[11451419];//ll要赋成-1，因为l,r可能等于0 struct node{ int l,r ...