C - Count Triangles 题意： 给定A,B,C,D,求 $ 1<=A<=x<=B<=y<=C<=z<=D $,满足x,y,z构成的三角形 思路： 枚举x+y的值设为i,则z的取值范围为 $ [C,min(D,i-1)] $ 因为 $ y=i-x且y∈[B,C]且x∈[A,B], $ $ 所以x∈[max(i-C,A),min(C,i...

模型 此类问题大多与拓扑序有关，可以拆成三种集合，环，环上带若干条链(基环树)，单条链(只有点数n>边数m存在) 例题 F. Selling a Menagerie 题意： c[i]表示i的价值，当i在a[i]前面出现时，i的贡献价值为2*c[i]，否则为c[i],求一个顺序使总价值最大，所有a[i],i<=n 思路： i向a[i]连边,先做个拓扑序,剩下还有数说明有环，在环内找...

CF1864 A. Increasing and Decreasing 建一个数组， $ a_1=x,a_n=y ,b_i=a_{i+1}-a_i$ ，a单调递增，b单调递减。 思路： 从后往前枚举每次减1，2，3,… 若 $ a_1<x $ ,输出-1，否则输出数组 void solve(){ int x,y,n; cin>>x>>y>>n; ...

F. Magic Will Save the World 题意： 每一秒钟可以生产w个水元素和f个火元素，问需要多少秒才能消灭n个怪兽(攻击时间忽略不计，w或f大于怪兽的值可以攻击，并减少相应的值，可以同时消灭多个怪兽) 思路： 枚举n个怪兽能组成的所有值(可以用01背包求出来)，定义这一部分需要水元素消灭，剩下的用火元素消灭。 复杂度： $O(N \cdot sum) $ void sol...

P6538回首过去 题意： 求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le n$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。 Subtask 1（40 分），$1 \le n \le 10^3$； Subtask 2（40 分），$1 \le n \le 10^7$； Subtask 3（20 分），$1 \le n \le 10^{12...

CF1872 D. Plus Minus Permutation(思维) 题意： 给定三个整数n,x,y,定义一个permutation的价值是: $(p_{1 \cdot x}+p_{2 \cdot x}+…+p_{i \cdot x})-(p_{1 \cdot y}+…+p_{j \cdot y}) $ ,其中 $i \cdot x<=n$, $j \cdot y<=n...

B - A Trivial Problem（数论+二分查找） 题意：给定一个整数m,找出整数N使N！有m个后导0 思路：将 $N!$ 分解因数必定得到 $10^m$ ，而10可以拆成2*5，m即为质因数中2和5的指数最小值易知2的指数必定比5的指数大 因此题目化简为有几个N使N！的阶层5的指数为m 可以二分查找，复杂度 $O(log(1e9))$ void solve(){ int n; ...

CF1866 A - Ambitious Kid 题意：每次操作能使数组一个数减1或加1，问最小操作数使 $a_1 \cdot a_2 \cdot …. \cdot a_n=0$ 思路：求最小绝对值 void solve(){ int n; int ans=INF; cin>>n; for(int i=1,x;i<=n;i++){ cin>>x; ...

CF1861 A. Prime Deletion 题意： 一串9个数字，1-9只出现一次，删除若干个字符，使数字为质数 思路： 1在3前输出13，3在1前输出31 #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for(int i = 0; i <...

CF1770 A. Koxia and Whiteboards 题意： 给定长度为n的数组a，m次操作，第i次操作用 $b_i$ 替换数组任意数，求数组最后的最大总和 思路： 优先队列建小根堆，每次弹出最小值，加入 $b_i$ void solve(){ int n,m; cin>>n>>m; priority_queue<int,vector<in...