賽時爆炸了，很多平常熟悉的套路都沒想起來，但題目還是要補的不是嗎？
T1
題意：給一個(ge) 長度為(wei) 的數組 ，若相鄰兩(liang) 數之差的絕對值不超過 則可以交換，問能得到的所有 中字典序最小的一個(ge) 。
數據範圍：
發現 的數無法交換，於(yu) 是找到所有這樣的限製做拓撲排序。如何做？正常最小拓撲序是把所有入度為(wei) 0的點放入優(you) 先隊列中，然後每次取堆頂的點並從(cong) 圖中刪除。時間複雜度為(wei) 。
思考一下如何優(you) 化，首先可以對原數組離散化，用一個(ge) 線段樹來維護當前可能的最小位置，每次取出作為(wei) 答案並更新與(yu) 其有連邊的點的入度即可。具體(ti) 地，若當前點的權值為(wei) ，則 中的所有權值對應的點的入度 。需要一個(ge) 帶懶標記線段樹做區間更新。
時間複雜度：
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e5+5;
int n,K,a[N],val[N],deg[N];
unordered_map <int,int> vis;
#define ls (p<<1)
#define rs (ls|1)
#define mid ((L+R)>>1)
pii t[N<<2];
int tag[N<<2];
inline pii Min(const pii a,const pii b){
if(a.se == b.se)return make_pair(min(a.fi,b.fi),a.se);
return a.se < b.se ? a : b;
}
void build(int p,int L,int R){
if(L == R){
t[p] = make_pair(L,deg[L]);
return;
}
build(ls,L,mid),build(rs,mid+1,R);
t[p] = Min(t[ls],t[rs]);
}
void push(int p,int v){tag[p] += v,t[p].se += v;}
void down(int p){
if(!tag[p])return;
push(ls,tag[p]),push(rs,tag[p]);
tag[p] = 0;
}
void upd(int p,int L,int R,int l,int r,int v){
if(l > R || r < L)return;
if(l <= L && R <= r){
push(p,v);
return;
}
down(p);
upd(ls,L,mid,l,r,v),upd(rs,mid+1,R,l,r,v);
t[p] = Min(t[ls],t[rs]);
}
int T[N];
void add(int x){for(;x <= n;x += x & -x)T[x]++;}
int Q(int x){
int res = 0;
for(;x;x -= x & -x)res += T[x];
return res;
}
int main(){
n = read(),K = read();
rep(i,1,n)a[i] = read(),val[i] = a[i];
sort(val+1,val+n+1);
rep(i,1,n){
vis[a[i]]++;
a[i] = lower_bound(val+1,val+n+1,a[i]) - val + vis[a[i]] - 1;
}
//calculating in-degree
rep(i,1,n){
int x = lower_bound(val+1,val+n+1,val[a[i]]-K) - val - 1;
int y = lower_bound(val+1,val+n+1,val[a[i]]+K+1) - val - 1;
deg[a[i]] = (i-1) + Q(x) - Q(y);
add(a[i]);
}
build(1,1,n);
rep(i,1,n){
int u = t[1].fi;
cout << val[u] << 'n';
int x = lower_bound(val+1,val+n+1,val[u]-K) - val - 1;
//cout << 1 << ' ' << x << 'n';
int y = lower_bound(val+1,val+n+1,val[u]+K+1) - val - 1;
//cout << y+1 << ' ' << n << 'n';
//cout << u << ' ' << u << 'n';
upd(1,1,n,1,x,-1);
upd(1,1,n,y+1,n,-1);
upd(1,1,n,u,u,n);
}
return 0;
}
T2
題意：給一個(ge) 長度為(wei) 的數組 ，相鄰兩(liang) 項若差不大於(yu) 1則可以交換，問能得到的不同 個(ge) 數，答案模 。
數據範圍：
計數問題基本就是 dp 了。發現從(cong) 上一題中的不大於(yu) 變成了不大於(yu) ，必然有貓膩。由於(yu) 差大於(yu) 的數很多，所以大部分數之間是不能夠對換位置的，考慮從(cong) 這一點入手解決(jue) 問題。
然後此時如果觀察到了奇數之間不可能調換位置（除非兩(liang) 數相同，但是這樣的調換沒有意義(yi) ），偶數也同理。於(yu) 是設計 dp 狀態為(wei) 表示當前確定了前 個(ge) 位置，有 個(ge) 奇數， 個(ge) 偶數。對每個(ge) 數，預處理它最遠能與(yu) 它不同奇偶性的哪個(ge) 數交換即可。轉移是簡單的。
時間複雜度： 。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=5e3+5,P = 1e9+7;
int n,a[N],pos[N];
void add(int &x,const int y){x += y;if(x > P)x -= P;}
void sub(int &x,const int y){x -= y;if(x < 0)x += P;}
void solve(){
n = read();
vector <int> even,odd;
rep(i,1,n){
a[i] = read();
if(a[i] & 1){
pos[i] = sz(odd);
odd.pb(i);
}else{
pos[i] = sz(even);
even.pb(i);
}
}
vector <int> pre(n+1);
rep(i,1,n){
if(a[i] & 1)pre[i] = sz(even);
else pre[i] = sz(odd);
rep(j,i+1,n)if(((a[i] - a[j]) & 1) && abs(a[i] - a[j]) > 1){
pre[i] = min(pre[i],pos[j]);
}
}
vector <vi> dp(sz(even) + 1,vi(sz(odd) + 1));
dp[0][0] = 1;
rep(i,0,sz(even))rep(j,0,sz(odd)){
if(!dp[i][j])continue;
if(i < sz(even) && j <= pre[even[i]])
add(dp[i+1][j],dp[i][j]);
if(j < sz(odd) && i <= pre[odd[j]])
add(dp[i][j+1],dp[i][j]);
}
cout << dp[sz(even)][sz(odd)] << 'n';
}
int main(){
int T = read();
while(T--)solve();
return 0;
}
T3
題意：給定 組向量，求每一組中選出一個(ge) 向量，加起來後最大的長度。
數據範圍：向量數不超過 ， 。
我們(men) 維護當前所有可能答案構成的點集，有
性質1：如果一個(ge) 點不在該點集的凸包上，那麽(me) 這個(ge) 點離原點的距離不是最大的。
對每一組向量我們(men) 都可以求出它的凸包。對於(yu) 第 組向量，我們(men) 將它的凸包與(yu) 前 組得到的答案凸包合並，用 Minkowski 和即可。
時間複雜度： 。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e5+5;
struct node{
ll x,y;
node operator - (const node a){return (node){x-a.x,y-a.y};}
node operator + (const node a){return (node){x+a.x,y+a.y};}
ll operator * (node a)const{return x*a.y - y*a.x;}//cross pro
ll len()const{return x*x + y*y;}
}O;
bool cmpy(const node &a,const node &b){return a.y == b.y ? a.x < b.x : a.y < b.y;}
bool cmp(const node &a,const node &b){return a*b == 0 ? a.len() < b.len() : a*b > 0;}
int n,m,q,stk[N],top,tot;
void Convex(vector <node> &A){
sort(A.begin(),A.end(),cmpy);
O = A[0];
stk[top=1] = 0;
rep(i,0,sz(A)-1)A[i] = A[i] - O;
sort(A.begin()+1,A.end(),cmp);//極角排序
rep(i,1,sz(A)-1){
while(top > 1 && (A[i] - A[stk[top-1]]) * (A[stk[top]] - A[stk[top-1]]) >= 0)top--;
stk[++top] = i;
}
rep(i,1,top)A[i-1] = A[stk[i]] + O;
A.resize(top);
//rep(i,0,sz(A)-1)cout << A[i].x << ' ' << A[i].y << 'n';
A.pb(A[0]);
}
vector <node> A,B,vec[N],dA,dB,ans,tmp;
void Minkowski(vector <node> &A,vector <node> &B){
dA.resize(sz(A)),dB.resize(sz(B));
rep(i,0,sz(A)-1)dA[i] = A[(i+1)%sz(A)] - A[i];
rep(i,0,sz(B)-1)dB[i] = B[(i+1)%sz(B)] - B[i];
ans.pb(A[0] + B[0]);
int a = 0,b = 0;
while(a < sz(A) && b < sz(B)){
if(dA[a] * dB[b] >= 0)ans.pb(ans.back() + dA[a++]);
else ans.pb(ans.back() + dB[b++]);
}
while(a < sz(A))ans.pb(ans.back() + dA[a++]);
while(b < sz(B))ans.pb(ans.back() + dB[b++]);
}
int main(){
n = read();
rep(i,1,n){
int x = read();
rep(j,1,x)vec[i].pb((node){read(),read()});
Convex(vec[i]);
}
ans = vec[1];
rep(i,2,n){
tmp = ans;ans.clear();
Minkowski(vec[i],tmp);
Convex(ans);
}
ll len = 0;
for(auto t : ans)len = max(len,t.len());
cout << len << 'n';
return 0;
}
賽後總結：
這次比賽對時間的把控極為(wei) 失敗，不應該因為(wei) 看到了熟悉/感覺能做的題目就一直死磕在上麵，這對比賽是極其不利的，希望以後能學會(hui) 合理利用時間。除了T3的計算幾何對USACO是相對新穎的考點，另外兩(liang) 題並沒有什麽(me) 新的東(dong) 西，T3也容易在了解一點知識後套模板解決(jue) 。
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。