T1 字符串构造机
考虑将一个 LCP 条件拆分成两个，一个是相等的部分，使用并查集维护，另一个是不等的部分，两个串末尾的字符一定不相等，随便那啥维护。对于非法情况就是在同一个相等联通块内有不相等的条件。然后考虑从前往后贪心即可。
#include<bits/stdc++.h>
using namespace std;
#define p pair<int, int>
constexpr int N = 1e3 + 5;
int n, m, s[N], f[N], g[N][2], tot;
inline int find(int k){ return f[k] ? f[k] = find(f[k]) : k; }
vector<int> G[N]; bitset<N> st;
int main(){
freopen("str.in", "r", stdin); freopen("str.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1, x, y, z; i<=m; ++i){
cin>>x>>y>>z; if(x > y) swap(x, y);
int l1 = x, l2 = y, r1 = x+z-1, r2 = y+z-1;
if(x == y) continue;
if(r2+1 <= n) g[++tot][0] = r1+1, g[tot][1] = r2+1;
for(int u=l2, v=l1; u<=r2; ++u, ++v){
int fa = find(u), fb = find(v);
if(fa == fb) continue;
f[fa] = fb;
}
} memset(s, 0xff, sizeof(int) * (n+1));
for(int i=1; i<=tot; ++i){
int u = find(g[i][0]), v = find(g[i][1]);
if(u == v) return cout<<"-1", 0;
G[u].push_back(v), G[v].push_back(u);
}
for(int i=1; i<=n; ++i){
int fa = find(i);
if(s[fa] == -1){
st.reset();
for(int v : G[fa]) if(s[find(v)] != -1)
st[s[find(v)]] = 1;
int cnt = 0;
while(st[cnt]) ++cnt;
s[fa] = cnt;
} s[i] = s[fa];
}
for(int i=1; i<=n; ++i) cout<<s[i]<<' ';
return 0;
}
T2 忍者小队
最大值是简单的。找到所有 \(k\) 的倍数并取个 gcd，如果这个 gcd 不为 \(k\)，那么不存在合法的最大最小。否则最大值就为倍数的数量。
考虑最小值答案值域，一定为 \(1\sim 7\)。因为最多质数组成数最大仅为 \(2*3*5*7*11*13*17\)。那么令 \(f_{i,k}\) 表示有 \(i\) 个数 gcd 为 \(k\) 的方案数。考虑容斥，有：
\[f_{i,j}=\binom{cnt}{i}-\sum_{j=2k,j|k}^{V}f_{i,j} \]其中 \(cnt\) 为倍数数量。用方案数来 check 即可。
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 3e5 + 5, M = 1e9 + 7;
int n, m, a[N], val[N], mx, f[8][N], ans[N][2], C[N][8], tot[N];
inline int add(initializer_list<int> Add){
int res = 0;
for(int v : Add) res = res + v >= M ? res + v - M : res + v;
return res;
}
int main(){
freopen("sor.in", "r", stdin); freopen("sor.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m; for(int i=1; i<=n; ++i) cin>>a[i], ++val[a[i]], mx = max(mx, a[i]);
for(int i=0; i<=n; ++i) C[i][0] = 1;
for(int i=1; i<=n; ++i) for(int j=1; j<=7; ++j) C[i][j] = add({C[i-1][j], C[i-1][j-1]});
for(int i=1; i<=mx; ++i) ans[i][0] = 114514;
for(int k=1; k<=mx; ++k){
int tmp = 0, sum = 0;
for(int i=1; i*k<=mx; ++i) if(val[i*k])
tmp = __gcd(tmp, i), sum += val[i*k];
tot[k] = sum;
if(tmp ^ 1) { ans[k][1] = ans[k][0] = -1; continue; }
ans[k][1] = sum; if(val[k]) ans[k][0] = 1;
}
for(int k=mx; k>=1; --k){
for(int i=1; i<=7; ++i){
f[i][k] = C[tot[k]][i];
for(int j=k*2; j<=mx; j+=k) f[i][k] = add({f[i][k], M-f[i][j]});
if(f[i][k] && ans[k][0] == 114514) ans[k][0] = i;
}
}
for(int i=1; i<=m; ++i) cout<<ans[i][0]<<' '<<ans[i][1]<<'\n';
return 0;
}
T3 狗卡
来不及写了……
标签：11,2024.11,14,noip,int,res,sum,len,vec From： https://www.cnblogs.com/xiaolemc/p/18549616