A
我们考虑序列的最后一个数字 $x$，那么 $>x$ 的数字在排名中就没有贡献了，所以我们只能让前面 $<x$ 的数尽量靠前。贪心的想我们肯定让这个 $x$ 尽量大，也就是说如果把越大的数放在后面，那么就会有更多小的数在前面。
于是答案等价于求反过来的最大字典序。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e5 +5;
std::vector<int> G[MAXN];
int deg[MAXN];
int n,m;
inline void Solve(){
scanf("%d%d",&n,&m);
FOR(i,1,n) G[i].clear();
FOR(i,1,n) deg[i] = 0;
FOR(i,1,m){
int u,v;scanf("%d%d",&u,&v);
G[v].pb(u);++deg[u];
}
std::priority_queue<int> q;
FOR(i,1,n) if(!deg[i]) q.push(i);
std::vector<int> ans;
while(!q.empty()){
int v = q.top();q.pop();ans.pb(v);
for(auto x:G[v]){
if(!--deg[x]){
q.push(x);
}
}
}
std::reverse(all(ans));
if(ans.size() != n) puts("Impossible!");
else{
for(auto x:ans) printf("%d ",x);
puts("");
}
}
int main(){
int T;scanf("%d",&T);
while(T--) Solve();
return 0;
}B
暴力做法是枚举两位后在哈希表里查一下，复杂度 $O(n\log^2 a_i)$。
注意到我们可以分开枚举，枚举 $a$ 的某一位，将对应的数插入到哈希表，然后枚举 $b$ 的某一位查询，注意要减掉多算的，复杂度 $O(n \log a_i)$。注意这样会把 $a_i=b_i$ 多算 $\log a_i$ 次，特判一下就行。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<LL,LL>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e5 + 5;
int n,m,a[MAXN],b[MAXN];
const int mod = 19260817;
std::mt19937 g(time(NULL));
int BASE;
inline char nc(){
#define SIZE 1000000+3
static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
if(p1 == p2){
p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
if(p1 == p2) return -1;
}
return *p1++;
#undef SIZE
}
template <typename T>
inline void read(T &x){
x = 0;int flag = 0;char ch = nc();
while(!isdigit(ch)){
if(ch == '-') flag = 1;
ch = nc();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + (ch^'0');
ch = nc();
}
if(flag) x = -x;
}
struct HASH{
struct Edge{
int val,cnt,nxt;
}e[MAXN];
int head[mod],cnt = 0;
inline void insert(int x){
x ^= BASE;
int b = x%mod;
for(int i = head[b];i;i = e[i].nxt){
if(e[i].val == x){
e[i].cnt++;
return;
}
}
e[++cnt] = (Edge){x,1,head[b]};head[b] = cnt;
}
inline int find(int x){
x ^= BASE;
int b = x%mod;
for(int i = head[b];i;i = e[i].nxt){
if(e[i].val == x) return e[i].cnt;
}
return 0;
}
}S;
int main(){
BASE = g()%((1<<30));
read(n);read(m);
FOR(i,1,n){
int x;read(x);S.insert(x);
}
LL ans = 0;
FOR(i,1,m){
int x;read(x);
FOR(a,0,29){
FOR(b,a+1,29){
ans += S.find(x^(1<<a)^(1<<b));
}
}
}
printf("%lld\n",ans);
return 0;
}C
这场CF的 E
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5e5 + 5;
const int ha = 1e9 + 7;
int k,n,m;
P a[2][MAXN];
std::vector<int> S;
int lim[2][MAXN];
int f[2][MAXN];
// 当前这一位是0/1 上一个不一样的在哪里
inline void add(int &x,int y){
x += y;if(x >= ha) x -= ha;
}
inline int qpow(int a,int n=ha-2){
int res = 1;
while(n){
if(n & 1) res = 1ll*res*a%ha;
a = 1ll*a*a%ha;
n >>= 1;
}
return res;
}
int main(){
scanf("%d%d%d",&k,&n,&m);
S.pb(0);S.pb(k);
FOR(i,1,n){
scanf("%d%d",&a[0][i].fi,&a[0][i].se);--a[0][i].fi;
S.pb(a[0][i].fi);S.pb(a[0][i].se);
}
FOR(i,1,m){
scanf("%d%d",&a[1][i].fi,&a[1][i].se);--a[1][i].fi;
S.pb(a[1][i].fi);S.pb(a[1][i].se);
}
CLR(lim,-1);
std::sort(all(S));S.erase(std::unique(all(S)),S.end());
FOR(i,1,n){
a[0][i].fi = std::lower_bound(all(S),a[0][i].fi)-S.begin();
a[0][i].se = std::lower_bound(all(S),a[0][i].se)-S.begin();
lim[0][a[0][i].se] = std::max(lim[0][a[0][i].se],a[0][i].fi);
}
FOR(i,1,m){
a[1][i].fi = std::lower_bound(all(S),a[1][i].fi)-S.begin();
a[1][i].se = std::lower_bound(all(S),a[1][i].se)-S.begin();
lim[1][a[1][i].se] = std::max(lim[1][a[1][i].se],a[1][i].fi);
}
int n = S.size();
FOR(i,0,1) FOR(j,1,n) lim[i][j] = std::max(lim[i][j],lim[i][j-1]);
f[0][0] = 1;int sm0 = 1,tp0 = 0,sm1 = 0,tp1 = 0;
FOR(i,0,n-2){
while(tp0 <= lim[1][i]) add(sm0,ha-f[0][tp0]),++tp0;
while(tp1 <= lim[0][i]) add(sm1,ha-f[1][tp1]),++tp1;
add(f[1][i],sm0);add(f[0][i],sm1);
int gx = qpow(2,S[i+1]-S[i]-1);add(gx,ha-1);
gx = 1ll*gx*(sm0+sm1)%ha;
add(f[0][i+1],gx);add(f[1][i+1],gx);
int t0 = sm0,t1 = sm1;
add(sm0,t1);add(sm1,t0);
add(sm0,gx);add(sm1,gx);
}
int ans = 0;
FOR(i,0,n) if(i > lim[1][n]) add(ans,f[0][i]);
FOR(i,0,n) if(i > lim[0][n]) add(ans,f[1][i]);
printf("%d\n",ans);
return 0;
}D
考虑这个条件等价于第 $i$ 个位置可以有一个容量是 $[a_i,b_i]$ 的物品，要求凑出 $p$ 的最小代价。
于是单调队列优化 dp 即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1000+5;
int n,a[MAXN],b[MAXN],c[MAXN],p;
LL f[2][10005];
int now;
inline void Solve(){
scanf("%d%d",&n,&p);
FOR(i,1,n) scanf("%d",a+i);
FOR(i,1,n) scanf("%d",b+i);
FOR(i,1,n) scanf("%d",c+i);
now = 0;CLR(f[now],0x3f);
f[now][0] = 0;
FOR(i,1,n){
CLR(f[now^1],0x3f);
std::deque<int> q;
FOR(j,0,p){
if(j-a[i] >= 0){
while(!q.empty() && f[now][q.back()] >= f[now][j-a[i]]) q.pop_back();
q.pb(j-a[i]);
}
while(!q.empty() && q.front() < j-b[i]) q.pop_front();
if(!q.empty()) f[now^1][j] = f[now][q.front()]+c[i];
f[now^1][j] = std::min(f[now^1][j],f[now][j]);
}
now ^= 1;
}
f[now][p] > 2e9 ? puts("IMPOSSIBLE!!!") : printf("%lld\n",f[now][p]);
}
int main(){
int T;scanf("%d",&T);
while(T--) Solve();
return 0;
}