FZU 2025 寒假集训个人题解
曾迷途才怕追不上满街赶路人 无人理睬如何求生
Div1 Day1
A
首先通过手玩可以知道,在 set
来动态维护每个集合的大小。如果我们这里大力做,枚举所有
但是我们实际上可以发现,我们考虑分组大小为
也就是说我们考虑所有质数即可,感觉很小()所以复杂度就
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e6 + 10;
struct fc {
ll x,y;
fc(ll a = 0,ll b = 0){x = a,y = b;}
friend inline bool operator < (const fc &a,const fc &b) {
return (ll)a.x * b.y < (ll)b.x * a.y;
}
}ans;
ll a[N],n,x;
void work(int k) {
// cerr << "nowk:" << k << "\n";
multiset <ll> s;
vector <ll> sum(k,0);
for (int i = 1;i < n;++i) {
sum[i % k] += a[i];
}
sum[0] += x;
for (int i = 0;i < k;++i) s.insert(sum[i]);
ll minn = *s.begin(),maxx = *s.rbegin();
fc now = fc(maxx,minn);
if (now < ans) ans = now;
int np = 0;
for (int i = 1;i < n;++i) {
s.erase(s.find(sum[np]));
sum[np] += a[i];sum[np] -= x;
s.insert(sum[np]);
++np;np %= k;
s.erase(s.find(sum[np]));
sum[np] -= a[i];sum[np] += x;
s.insert(sum[np]);
ll minn = *s.begin(),maxx = *s.rbegin();
fc now = fc(maxx,minn);
if (now < ans) ans = now;
// cerr << "debug:" << i << "\n";
// cerr << "np:" << np << "\n";
// cerr << "now:" << now.x << " " << now.y << "\n";
// for (int j = 0;j < k;++j) cerr << sum[j] << " ";
// cerr << "\n";
}
}
bool vis[1000010];
void solve() {
cin >> n >> x;
ans.x = 0x3f3f3f3f,ans.y = 1;
for (int i = 1;i < n;++i) {
cin >> a[i];
}
for (int k = 2;k <= n;++k) {
if (n % k == 0) {
if (!vis[k] || n == k) work(k);
}
}
int gccc = __gcd(ans.x,ans.y);
ans.x /= gccc,ans.y /= gccc;
cout << ans.x << " " << ans.y << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);//cout.tie(0);
for (int i = 2;i <= 1000000;++i) {
if (!vis[i]) {
for (int j = i*2;j <= 1000000;j += i) {
vis[j] = 1;
}
}
}
int T;cin >> T;
while (T--) solve();
return 0;
}
Div 1 Day 2
K
简单构造,考虑每一个连续段,记连续段长度为
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e5 + 10;
int k,n;
string s;
signed main() {
int ans = 0;
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> k >> s;n = s.size();
if (k == 2) {
int typ = 0,ans1 = 0,ans2 = 0;
for (int i = 0;i < n;++i) {
if (s[i] != typ + '0') ++ans1;
typ ^= 1;
}
typ = 1;
for (int i = 0;i < n;++i) {
if (s[i] != typ + '0') ++ans2;
typ ^= 1;
}
if (ans1 < ans2) {
ans = ans1;
typ = 0;
} else {
ans = ans2;
typ = 1;
}
for (int i = 0;i < n;++i) {
s[i] = typ + '0',typ ^= 1;
}
} else {
int lst = 0,typ = s[0] - '0';
for (int i = 1;i < n;++i) {
if (s[i] - '0' != typ) {
int len = i - lst;
// cerr << "len:" << len << "i,lst:" << i << " " << lst << "\n";
if (len >= k) {
//11111100 3
if (len % k == 0) {
for (int j = lst + k - 2;j < i;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
} else {
for (int j = lst + k -1;j < i;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
}
ans += len / k;
}
lst = i,typ = s[i] - '0';
}
}
int len = n - lst;
// cerr << "len:" << len << "i,lst:" << n << " " << lst << "\n";
if (len >= k) {
//11111100 3
if (len % k == 0) {
for (int j = lst + k - 2;j < n;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
} else {
for (int j = lst + k -1;j < n;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
}
ans += len / k;
}
}
cout << ans << " " << s;
return 0;
}
I
手玩出来的神秘结论……首先我们把相切的两个圆建边。
首先你考虑有环肯定不行,有一条偶链肯定也不行,因为偶链中增加的点数恰好等于减少的点数。
不难发现只有奇链对我们的答案有贡献,那么其实本质上就是一个判断二分图的过程,对于每个连通块判断一下就OK。
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e3 + 10;
struct poi {
ll x,y,r;
}p[N];
int n;
vector <int> G[N];
int col[N],cnt[3];
bool vis[N],flag;
ll dis(poi a,poi b) {
ll x = a.x - b.x,y = a.y - b.y;
return x * x + y * y;
}
void dfs(int x,int c) {
col[x] = c;cnt[c]++;
for (auto y : G[x]) {
if (!col[y]) {
dfs(y,3-c);
} else {
if (col[y] == col[x]) {
flag = 1;
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1;i <= n;++i) {
cin >> p[i].x >> p[i].y >> p[i].r;
}
for (int i = 1;i <= n;++i) {
for (int j = i + 1;j <= n;++j) {
if (dis(p[i],p[j]) == (p[i].r + p[j].r) * (p[i].r + p[j].r)) {
G[i].push_back(j);G[j].push_back(i);
}
}
}
bool qwq = 1;
for (int i = 1;i <= n;++i) {
if (!col[i]) {
flag = 0;cnt[2] = cnt[1] = 0;
dfs(i,1);
if (!flag && cnt[1] != cnt[2]) {
// cerr << i << "\n";
// cerr << flag << " " << cnt[1] << " " << cnt[2] << "\n";
qwq = 0;
}
}
}
if (qwq) cout << "NO";
else cout << "YES";
return 0;
}
EG神人tv题。
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭