6-30
GCD
有 R − L + 1 个整数,分别为 L, L + 1, . . . , R − 1, R。你可以做如下操作最多 K 次:• 选择其中两个数 a, b,删掉它们,并往里面插入一个新的数 a × b。请判断是否可以让剩余所有数的 GCD 不为 1。该题存在 T 组数据。
显然,让所有数的最大公约数为2是最优的,那么判断区间奇数个数 ⌊ R+1/2 ⌋ − ⌊ L/2 ⌋ 是否 ≤ K 即可。
std:
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define pE() puts("") #define W(x) write(x) #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } int T, l, r, k; int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); T = rd(); while (T --) { l = rd(); r = rd(); k = rd(); int len = r - l + 1; int sum; if (len == 1) { if (l == 1) printf("NO\n"); else printf("YES\n"); continue; } else if (len % 2 == 0) sum = len / 2; else if (l % 2 == 0) sum = (len - 1) / 2; else sum = (len + 1) / 2; if (sum <= k) printf("YES\n"); else printf("NO\n"); } return 0; }
T2MEX
对于一个可重非负整数集 S,MEX(S) 表示这个集合中,没有出现的最小非负整数。例如 MEX({0, 0, 1, 3}) = 2, MEX({0}) = 1, MEX({}) = 0。黑板上有 N 个非负整数,第 i 个非负整数为 Ai。
你需要做下列操作恰好 K 次:
• 从黑板上选择零个或者若干个数,设它们组成的可重非负整数集 S,你将在黑板上写上 MEX(S) 这个数。请求出最后黑板上留下的数字有多少种情况,两种情况不同当且仅当存在某一个数字在两种情况中出现次数不同,答案对 998244353 取模
我们只要先都插入 m,然后都插入 < m 的数,这样一定能得到所有最终可能集合,还不会算重。枚举插入了 i 次 m,当前 MEX 为 mi,答案为 ∑K i=0 (mi+K−i−1mi−1 ) 。
std:
#include <bits/stdc++.h> #define int long long using namespace std; const int INF=1e6+5; const int Mod=998244353; int n,k,a[INF],num[INF],fav[INF],ifav[INF]; int ksm(int x,int y) { int ba=x%Mod,ans=1; while (y) { if (y&1) ans=(ans*ba)%Mod; ba=(ba*ba)%Mod;y>>=1; } return ans; } void init() { fav[0]=1;int N=1e6; for (int i=1;i<=N;i++) fav[i]=fav[i-1]*i%Mod; ifav[N]=ksm(fav[N],Mod-2); for (int i=N-1;~i;i--) ifav[i]=ifav[i+1]*(i+1)%Mod; } int C(int x,int y) { if (x<y) return 0; return fav[x]*ifav[y]%Mod*ifav[x-y]%Mod; } signed main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>k;int kk=k;init(); for (int i=1;i<=n;i++) cin>>a[i],num[a[i]]++; int ans=0; for (int i=0;i<=5e5;i++) { int fl=0; if (!num[i]) {kk--;fl=1;} if (kk<0) break; if (fl) ans+=C(kk+i,i),ans%=Mod; else ans+=(C(kk+i,i)-C(kk+i-1,i-1))%Mod,ans%=Mod; } ans%=Mod;ans+=Mod;ans%=Mod; cout<<ans<<"\n"; return 0; }
T3XOR
有一个长度为 N 的二元组序列 ((A1, B1),(A2, B2), . . . ,(AN , BN ))。 你需要进行 N/2 次删除操作将整个序列删空。对于每次删除操作,你需要选择一对相邻的二元组,将它们从序列中移除,再将前后的序列拼接成一个序列。 要求对于删除的每对二元组 (Ax, Bx),(Ay, By) (x < y) 中,都满足要求: • Ax xor By = Bx xor Ay • Ax + Bx ≤ K
不考虑第二个要求用队列模拟有80分,考虑正解,现在对于每个括号可以任意作为左括号或右括号,那么可以贪心地进行多种类括号匹配:
• 维护一个栈,按 i = 1, 2, . . . , N 的顺序每次往栈顶放入 Ai xor Bi。 • 每次放入元素后,如果栈顶两个元素相同,那么同时将它们弹出栈。 Cx = 0 的条件,可以看作是若 Ci = 1,那么这个元素被删除时只能在右边,也就是一定是右括号。现在一些括号可以自由定向,一些是右括号,从左往右扫似乎不好控制。此时我们从右往左扫,贪心地来说,对于一个右括号,扫到左边第一个可匹配的就匹配一定最优std:
#include <bits/stdc++.h> #define int long long using namespace std; const int INF=1e6+5; int n,a[INF],k,b[INF],c[INF],d[INF],q[INF]; void solve() { cin>>n>>k;int r=0; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++) cin>>b[i]; for (int i=n;i;i--) { c[i]=a[i]^b[i]; d[i]=a[i]+b[i]; } r=0; for (int i=n;i;i--) { // if (n==4) // cerr<<c[q[r]]<<" "<<d[i]<<" ok?\n"; if (c[q[r]]==c[i] && r && d[i]<=k) r--; else q[++r]=i; } // for (int i=1;i<=r;i++) // cerr<<q[i]<<" "; // cerr<<" endl\n"; if (r) cout<<"YES\n"; else cout<<"NO\n"; } signed main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int t=0;cin>>t; while (t--) solve(); return 0; }
T4RAY
Era 在一个大小为 H × W 的矩阵中,矩阵第 i 行第 j 列的格子坐标为 (i, j)。 有 Q 束射线穿过矩阵,第 i 束射线可由三个整数 Ti , Di , Xi 表示,意义如下: • 这束射线在第 Ti 秒时出现,然后立即消失。 • 当 Di = 0 时,这束射线恰好竖直穿过第 Xi 列的所有格子。 • 当 Di = 1 时,这束射线恰好水平穿过第 Xi 行的所有格子。 被射线击中可不妙,Era 需要在矩阵中移动来躲避射线。Era 每一次可以向上下左右移动一格,具体地,一次移动规则如下: • Era 当前所在坐标为 (x, y)。 • 若 (x − 1, y) 在矩阵内,Era 可以选择移动到 (x − 1, y)。 • 若 (x + 1, y) 在矩阵内,Era 可以选择移动到 (x + 1, y)。 • 若 (x, y − 1) 在矩阵内,Era 可以选择移动到 (x, y − 1)。 • 若 (x, y + 1) 在矩阵内,Era 可以选择移动到 (x, y + 1)。 Era 可以在一秒钟移动任意次数(也可以不移动),被击中当且仅到 Era 在某束射线出现时,正好位于这束射线穿过的行或列中。Era 最初所在矩阵中的位置可以自由选择,请求出 Era 全避射线最少需要移动多少次。我们可以按照时间从后往前 DP,设第 i 秒在第 j 格在之后还需移动 fi,j 次,对于每个状态暴力枚举其它所有的格子转移,时间复杂度 O(|Ti |(N2 + M2 ))。实际上,对于每个格子,只需对左右两边最近的下一秒不会被射线击中的格子转移即可,可以简单用反证法证明,然而总的有用转移数是 O(Q) 的,所以我们不需要记录时间这一维状态,每次将当前秒每段连续射线所包含的格子转移即可
std:
#include <bits/stdc++.h> #define int long long using namespace std; const int INF=1e6+5; struct P3 { int t,d,x; }aa[INF]; int n,m,f[INF],vis[INF],q,sum; signed main() { freopen("d.in","r",stdin); freopen("d.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m>>q; for (int i=1;i<=q;i++) cin>>aa[i].t>>aa[i].d>>aa[i].x; sort(aa+1,aa+1+q,[](P3 xx,P3 yy){return xx.t<yy.t;}); for (int i=1;i<=m;i++) f[i]=0; int la=0; for (int t=1;t<=1e5;t++) { int j=la;vis[0]=0; while (aa[j+1].t==t && j+1<=q) { j++; if (aa[j].d==1) vis[++vis[0]]=aa[j].x; } sort(vis+1,vis+1+vis[0],[](int x,int y){return x<y;}); for (int k=1;k<=vis[0];k++) { int r=k; while (vis[r+1]==vis[r]+1 && r+1<=vis[0]) r++; int Min=1e18; for (int l=k;l<=r;l++) Min=min(Min,f[vis[l]]-vis[l]); f[vis[r]+1]=min(f[vis[r]+1],vis[r]+1+Min); Min=1e18; for (int l=r;l>=k;l--) Min=min(Min,f[vis[l]]+vis[l]); f[vis[k]-1]=min(f[vis[k]-1],Min-(vis[k]-1)); for (int l=k;l<=r;l++) f[vis[l]]=1e18; k=r; } la=j; } int res=1e18; for (int i=1;i<=m;i++) res=min(res,f[i]); sum+=res; swap(n,m); for (int i=1;i<=q;i++) aa[i].d^=1; for (int i=1;i<=m;i++) f[i]=0; la=0; for (int t=1;t<=1e5;t++) { int j=la;vis[0]=0; while (aa[j+1].t==t && j+1<=q) { j++; if (aa[j].d==1) vis[++vis[0]]=aa[j].x; } sort(vis+1,vis+1+vis[0],[](int x,int y){return x<y;}); for (int k=1;k<=vis[0];k++) { int r=k; while (vis[r+1]==vis[r]+1 && r+1<=vis[0]) r++; int Min=1e18; for (int l=k;l<=r;l++) Min=min(Min,f[vis[l]]-vis[l]); f[vis[r]+1]=min(f[vis[r]+1],vis[r]+1+Min); Min=1e18; for (int l=r;l>=k;l--) Min=min(Min,f[vis[l]]+vis[l]); f[vis[k]-1]=min(f[vis[k]-1],Min-(vis[k]-1)); for (int l=k;l<=r;l++) f[vis[l]]=1e18; k=r; } la=j; } res=1e18; for (int i=1;i<=m;i++) res=min(res,f[i]); sum+=res; if (sum>1e17) cout<<"-1\n"; else cout<<sum<<"\n"; return 0; }
标签:std,vis,int,6.30,Era,2023,INF,集训,define From: https://www.cnblogs.com/determination/p/17521336.html