题意：

有一个计数器，一开始是0，每次操作可以把值+1或清零。 给若干已知条件表示第xi 次操作后计数器的值为vi，问是否有一种操作序列满足所有的已知条件

第i次操作过后,值是固定的，所有我们只要按操作顺序从小到大考虑,每次看前面最靠近它的是第几次操作以及值是多少,看能否在当前操作轮次变为当前数
怎么看呢?就看想要变成当前数,要么从前面最靠近它的那个值不断加+1,要么从某处开始变为0再不断+1,所以求出应该变为0的轮次,看能否在那个轮次变为0
注意,样例中存在a[i]=a[j]&&b[i]==b[j]的情况

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
void solve() {cin >> n >> m;map<int, int>mp;for (int i = 1; i <= m; i++) cin >> a[i] >> b[i];for(int i=1;i<=m;i++) {if(mp.count(a[i])&&mp[a[i]]!=b[i]){cout<<"No"<<endl;return;}mp[a[i]]=b[i];}int preu = 0, prev = 0;for (auto [u, v] : mp) {if (u - preu != v - prev) {if (prev == 0) {if (u - v < preu) {cout << "No" << endl;return;}} else {if (u - v < preu + 1) {cout << "No" << endl;return;}}}preu = u, prev = v;}cout << "Yes" << endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}

题意：

给定质数P和非负整数m，有多少非负整数g满足g≤m 且g⊕(P−1)≡1 (mod P)？这里 ⊕ 是按位异或（XOR） 运算符

首先关于一个模的trick:x%p=y,则x=k*p+y
^为异或
所以g^(p-1)=k*p+1g=(k*p+1)^(p-1)
然后求g=(k*p+1)^(p-1)<=m有多少个,其实就是求有多少个k
枚举k肯定是不可行的,因为m可达1e18,一定会超时,这种一般会用整除来计数

遇到异或，总归关于数学，先将有关于异或的式子以及性质全部列出来，根据题目选取有用的
a+b=（a^b）+  2 * （a&b）
(a&b）&（a^b）= 0
a^a=0
x=a^a^x
a^0=a
一个序列异或起来等于0，将序列分成两个集合，不管怎么分，两个集合内部异或起来得到的结果肯定相等
一个序列的异或和一定小于等于数值和（异或的本质是二进制下的不进位加法，相比起进位的普通加法，所得的结果当然会较小）==>a^b<=a+ba^b>=a-b
一个序列的数值和和异或和奇偶性相同
如果a^b已知=x或者a&b已知=y，那么要确定a和b，只要进行分配1即可
然后如果都没用到的话，大概是单独考虑每一位

可以根据不等式的关系进行放缩,先试试看
(k*p+1)^(p-1)<=(k*p+1+p-1)=(k+1)*p
如果(k+1)*p<=m,那么g=(k*p+1)^(p-1)一定小于等于m
得k<=m/p-1,也就是说当k<=m/p-1时,一定满足条件(k*p+1)^(p-1)>=(k*p+1-(p-1))=(k-1)*p+2
如果(k-1)*p+2>m,那么g一定大于m
得k>(m-2)/p+1,也就是说当k>(m-2)/p+1时,一定不满足条件所以,k在[0,m/p-1]均是满足条件的,在((m-2)/p+1,∞)均不满足条件,而中间的数是很少的,因为m/p-1和(m-2)/p是一个量级,枚举只要O(1),判断一下即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int p,m;
void solve() {cin>>p>>m;int ans=m/p;for(int k=m/p;k<=(m-2)/p+1;k++){if(((k*p+1)^(p-1))<=m) ans++;}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

有n个操作和m个变量，初始值均为0。 现在按1∼n的顺序执行这些操作，第i个操作会将其中pi 个变量赋值为i。 求一种不同于1∼n的执行顺序q，使得按照q1,q2,…,qn 的顺序执行操作会和原顺序得到一样的最终结果

一开始看了第一个样例的最后一行,想的是只要其中有一个操作中的所有位置只操作过一次,那么就可以了,但是后面一想,比如说,如果两次操作操作的都是位置3和   位置5,那么其实只要这两次操作的相对顺序不变,其它顺序完全可以改变的,其实说的就是一个严格的偏序关系,那么就指向了拓扑排序

来看两个关于拓扑排序字典序的例子:

拓扑排序的字典序问题 HDU1285 HDU4857_字典序 拓扑排序-CSDN博客

【HDU1285】

本题“要求输出时编号小的队伍在前”，本意就是字典序最小即可。

方法：拓扑排序，同时用优先队列（小顶堆），这样就能保证，拓扑序列不唯一时，编号小的优先，即字典序最小。

【HDU4857】

本题要求，拓扑序列不唯一时，让编号小的尽量靠前！这个意思不好好理解一下，很容易理解成字典序最小，然而不是！

1->4->2

1->3

很明显字典序最小的是 1 3 4 2

但却不是本题的答案，因为本题要求“编号小的尽量靠前”，编号2还可以提前的：1 4 2 3，才是正确的序列。

方法：反向建图，优先队列（大顶堆）求字典序最大的序列，倒着输出即为本题答案。

#理解#：

看上图，我们从1开始走，邻接点3和4,我们不知道后面还有个2，所以不知道3和4先选谁，故正向寻找是错的。

既然要求编号小的尽量靠前，那我们可以考虑把编号大的放到后面去。

我们反向走，从最后面往前走，优先走编号大的，也就是字典序最大。最后把序列倒着输出，如此，就满足了本题。

该题题目一开始的全排列是1,2,3,...n,也就是字典序最小,所以我们输出拓扑排序字典序最大,如果不是1,2,3,...n,那么就可以了
对于某个位置,它最终的值只由对该位置众多操作中的最后一次操作决定,所以仅仅对于该位置来说,前面的操作的顺序并不重要,只要最后一次操作在前面所有操作的后面即可,故前面所有操作的编号向最后一次操作的编号连一条边

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int d[N];
int n,m;
void solve() {cin>>n>>m;for(int i=1;i<=n;i++) d[i]=0;map<int,vector<int>>mp;vector<vector<int>>e(n+1);for(int i=1;i<=n;i++){int cnt;cin>>cnt;for(int j=0;j<cnt;j++){int x;cin>>x;mp[x].push_back(i);}}for(auto [_,res]:mp){int len=res.size();for(int i=0;i<len-1;i++){e[res[i]].push_back(res[len-1]);d[res[len-1]]++;}}priority_queue<int>q;for(int i=1;i<=n;i++){if(d[i]==0) q.push(i);}vector<int>ans;while(q.size()){int t=q.top();q.pop();ans.push_back(t);for(auto v:e[t]){d[v]--;if(d[v]==0) q.push(v);}}if((int)ans.size()<n){cout<<"No"<<endl;return;}bool ok=false;for(int i=0;i<(int)ans.size();i++){if(ans[i]!=i+1){ok=true;break;}}if(!ok) cout<<"No"<<endl;else{cout<<"Yes"<<endl;for(auto v:ans) cout<<v<<' ';cout<<endl;}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

其实呢,还有一种更简单的方法,就是判断是否可以相邻两个交换
因为相邻两个交换只作用在这两个上,不会影响其它的,当然只要存在一组相邻两个可以交换,就可以了,反过来,倘若一个都不存在,那么必定所有都不能动
判断两个相邻两个是否可以交换就看它们是否有交集,以及交集的位置的最后一次操作是否在它们之间,如果有交集并且交集的最后一次操作在它们之间.那么不能交换

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int ans[N];
set<int>s[N];
int n,m;
void solve() {cin>>n>>m;for(int i=1;i<=n;i++) ans[i]=i,s[i].clear();map<int,int>mp;for(int i=1;i<=n;i++){int cnt;cin>>cnt;for(int j=0;j<cnt;j++){int x;cin>>x;s[i].insert(x);mp[x]=i;//记录最后一次操作是多少}}for(int i=2;i<=n;i++){bool ok=true;for(auto v:s[i]){if(s[i-1].count(v)){//存在交集if(mp[v]==i||mp[v]==i-1){//交集的最后一次操作在它们之间ok=false;}}}if(ok){swap(ans[i],ans[i-1]);cout<<"Yes"<<endl;for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl;return;}}cout<<"No"<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

给定n件物品的体积wi 与价值vi，以及背包的总容量W。 你可以优先选择k件物品获得他们的价值，随后再选择一些 物品，要求随后选择的物品的体积之和不超过W。 最大化选择物品的价值之和

对于选择优先顺序,一个物品有两个属性
有这样一个trick:就是只考虑两个物品,然后定好它们俩的属性,考虑其中一个优先,再交换过来考虑一遍
考虑免费和花钱的优先级：
比如说其中一个物品(价格高,价值小),另一个物品(价格低,价值大),那么先考虑让第一个物品免费,让第二个物品花钱,很合理,因为花少的钱买价值大的,反过来,如果让第二个物品免费,让第一个物品花钱,那么就是花更多的钱买价值更小的,不优
比如说其中一个物品(价格高,价值大),另一个物品(价格低,价值小),那么肯定是优先让第一个物品免费,因为不用花钱就可以得到价值大的啊,然后再用少许的钱再得到一些价值综上,对于价格高的,免费一定是优先于花钱的,反过来则不优
一定要记住这样一个事实:对于价格高的,免费一定是优先于花钱的,反过来则不优,也就是说,我们按照价格升序之后,花钱的不能出现在任意一个免费的右边

先按照价格从小到大排序
接下来看两个例子:
比如说k=2,也就是说可以拿两个免费的物品1   2   3    4    5     6    7
花钱 花钱 不要 不要  花钱  免费  免费
一开始,我们对于最后两个体积最大的免费,对于1到5进行01背包,经过背包之后,1到5中有花钱的,有不要的
假设5的价值比6大,虽然5的价格没6高,但是我们可以选择5去免费,而6不要(k=2,只能装两个),为什么6不能去花钱呢?记住上面的事实,花钱的不能出现在免费的右边1   2   3    4    5     6    7免费  不要  免费
现在就变成这样了,免费的总价值变高了,然后对1到4进行01背包,由于免费的总价值变高了,虽然花钱买的总价值可能变小了,但是总体有可能变高,所以我们需要这样操作
综上,按价格升序之后,对1到i进行01背包,在i+1到n之中选择k个价值最高的
具体做法是利用优先队列预处理后缀选k个物品的价值之和的最大值,然后从前往后做一遍背包,前缀背包的最大值加上后缀最大值

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=5e3+10,M=1e4+10;
int dp[N][M];
int last[N];
int n,m,k;
struct node{int w,v;bool operator<(const node &W)const{return w<W.w;}
}q[N];
void solve() {cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>q[i].w>>q[i].v;sort(q+1,q+1+n);priority_queue<int,vector<int>,greater<int>>heap;for(int i=1;i<=n+1;i++) last[i]=0;int sum=0;for(int i=n;i>=1;i--){heap.push(q[i].v);sum+=q[i].v;while((int)heap.size()>k){int t=heap.top();heap.pop();sum-=t;}last[i]=sum;}int ans=last[1];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j]=dp[i-1][j];if(j>=q[i].w) dp[i][j]=max(dp[i][j],dp[i-1][j-q[i].w]+q[i].v);}ans=max(ans,dp[i][m]+last[i+1]);}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}