团队训练记录2024.10.7
赛时依然和本校强队差两题
比赛链接：https://codeforces.com/gym/104901
A. Many Many Heads
这里先用栈处理好第一个状况，然后根据层数进行第二个状况是否存在判断
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[250000];
vector<ll>g1[250000],g2[250000];
int main()
{
fio();
ll t;
cin>>t;
while(t--)
{
stack<pair<ll,ll>>q;
string f;
cin>>f;
for(ll i=0;i<f.size();i++)
{
if(f[i]==')')
f[i]='(';
if(f[i]==']')
f[i]='[';
g1[i].clear();
g2[i].clear();
}
for(ll i=0;i<f.size();i++)
{
if(q.empty())
{
q.push({f[i],i});
}
else if(q.top().first==f[i])
{
a[q.top().second]=i;
if(f[i]=='[')
f[i]=']';
else f[i]=')';
q.pop();
}
else
{
q.push({f[i],i});
}
}
ll cs=0;
ll pd=0;
priority_queue<ll,vector<ll>,greater<ll>>op;
for(ll i=0;i<f.size();i++)
{
if(op.empty())
{
op.push(a[i]);
cs++;
}
else
{
if(op.top()==i)
{
op.pop();
cs--;
if(f[i]==')')
{
if(g1[cs].size()>0)pd=1;
g1[cs].push_back(6);
}
else
{
if(g2[cs].size()>0)pd=1;
g2[cs].push_back(6);
}
}
else
{
cs++;
op.push(a[i]);
}
}
}
if(pd)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
D. Largest Digit
签到题，暴力即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll l1,r1,l2,r2;
ll cnt=0;
cin>>l1>>r1>>l2>>r2;
for(ll i=l1;i<=min(r1,l1+100);i++)
{
for(ll j=l2;j<=min(r2,l2+100);j++)
{
ll ans=0;
ans=j+i;
while(ans)
{
cnt=max(cnt,ans-ans/10*10);
ans/=10;
}
}
}
cout<<cnt<<endl;
}
}
G. Gifts from Knowledge
#include<bits/stdc++.h>
#define test(i) cout << #i << " "<< i << " " << endl;
using namespace std;
typedef long long ll;
const ll N = 3e6 + 10;
const ll mod = 1e9 + 7;
ll t, n, m;
string str[N];
ll a[N];
vector<ll> vis[N];
void fio() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void init_set(int n) {
for (int i = 0; i <= 2 * n + 1; i++) {
a[i] = i;
}
}
int find_set(int x) {
if (x != a[x]) a[x] = find_set(a[x]); //压缩路径
return a[x];
}
void merge_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x != y) a[x] = y; //x以y为父
}
signed main()
{
fio();
cin >> t;
while (t--) {
cin >> n >> m;
init_set(n+5);
for (int i = 0; i <= m; i++) {
vis[i].clear();
}
for (int i = 1; i <= n; i++) {
cin >> str[i];
}
//i是不翻，i+n翻
ll flag = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
if (str[i][j] == '1') {
vis[j + 1].push_back(i);
}
}
}
for (int i = 1; i <= m; i++) {
//cout << vis[i].size() << endl;
if (vis[i].size() + vis[m - i + 1].size() > 2) {
flag = 1;
}
if (vis[i].size() == 1&&vis[m-i+1].size()>0) {
merge_set(vis[i][0], vis[m - i + 1][0]);
merge_set(vis[i][0] + n, vis[m - i + 1][0] + n);
}
else if (vis[i].size() == 2) {
merge_set(vis[i][0] + n, vis[i][1]);
merge_set(vis[i][0], vis[i][1] + n);
}
}
for (int i = 1; i <= n; i++) {
if (find_set(i) == find_set(i + n)) flag = 1;
}
if (flag) {
cout << 0 << endl;
continue;
}
ll ans = 1;
ll cc = 0;
for (int i = 1; i <= 2 * n; i++) {
if (a[i] == i) {
cc++;
}
}
cc /= 2;
//cout << cc << endl;
while (cc) {
cc--;
ans %= mod;
ans *= 2;
ans %= mod;
}
cout << ans % mod << endl;
}
return 0;
}
I. Strange Sorting
对于一个左边界，右边界越大越好
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[250];
vector<pair<ll,ll>>g;
int main()
{
fio();
ll t;
cin>>t;
while(t--)
{
g.clear();
ll n;
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i];
while(1)
{
ll l=0,r=0;
for(ll i=1;i<=n;i++)
{
if(a[i]!=i)
{
l=i;
break;
}
}
if(l==0)
break;
for(ll i=n;i>=1;i--)
{
if(a[i]<a[l])
{
r=i;
break;
}
}
g.push_back({l,r});
sort(a+l,a+r+1);
}
cout<<g.size()<<endl;
for(auto j:g)
{
cout<<j.first<<" "<<j.second<<endl;
}
}
}
K. Rainbow Subarray
双set容器版：
其实中位数就是数组中从小到大较为中间的数，所以直接用原本一个set能存的数变成两个
set存的数即可，维护中间断点。
#include<iostream>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll maxn = 5e5 + 10;
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[500005];
map<ll, ll>q;
set<pair<ll, ll>>f, k;
void insert(ll x, ll y)
{
if (k.size() == 0)
{
k.insert({ x,y });
return;
}
else if (x >= (*k.rbegin()).first)
{
f.insert({ x,y });
while (f.size() >= k.size()+1)
{
auto j = f.begin();
k.insert({ (*j).first,(*j).second });
f.erase({ (*j).first,(*j).second });
}
}
else
{
k.insert({ x,y });
while (f.size() + 2 <= k.size())
{
auto j = k.rbegin();
f.insert({ (*j).first,(*j).second });
k.erase({ (*j).first,(*j).second });
}
}
}
void dt(ll x, ll y)
{
if (f.find({ x,y }) != f.end())
{
f.erase({ x,y });
while (f.size() + 2 <= k.size())
{
auto j = k.rbegin();
f.insert({ (*j).first,(*j).second });
k.erase({ (*j).first,(*j).second });
}
}
else
{
k.erase({ x,y });
while (f.size() >= k.size() + 1)
{
auto j = f.begin();
k.insert({ (*j).first,(*j).second });
f.erase({ (*j).first,(*j).second });
}
}
}
ll ck(ll sz)
{
return (*k.rbegin()).first;
}
int main()
{
fio();
ll t;
cin >> t;
while (t--)
{
k.clear();
f.clear();
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
a[i] -= i;
}
ll cnt = 0;
deque<ll>co;
ll sz = 0;
ll ans = 0;
ll op;
ll an = 1;
for (ll i = 1; i <= n; i++)
{
if (co.empty())
{
insert(a[i], i);
co.push_back(i);
sz++;
op = ck(sz);
ans = 0;
}
else
{
co.push_back(i);
ans += abs(a[i] - op);
insert(a[i], i);
sz++;
ll mid = ck(sz);
if (mid > op)
{
ans += ((sz - 1) / 2) * abs(op - mid);
ans -= (sz - ((sz - 1) / 2)) * abs(op - mid);
}
else if (mid < op)
{
ans -= ((sz + 1) / 2) * abs(op - mid);
ans += (sz - (sz + 1) / 2) * abs(op - mid);
}
while (!co.empty() && ans > m)
{
op = mid;
ans -= abs(a[co.front()] - mid);
dt(a[co.front()], co.front());
sz--;
if (sz == 0)
{
co.pop_front();
break;
}
mid = ck(sz);
if (mid > op)
{
ans -= ((sz + 1) / 2) * abs(op - mid);
ans += (sz - (sz + 1) / 2) * abs(op - mid);
}
op = mid;
co.pop_front();
}
op = mid;
an = max(an, (ll)co.size());
}
}
cout << an << endl;
}
}
线段树版：
用权值线段树+离散化实现中位数查找，然后维护一个中位数即可
//不用主席树，用权值线段树+离散化照样可以，qoj1000ms多过了
#include<iostream>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll maxn = 5e5 + 10;
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct s
{
ll l, r;
ll cs;
}p[maxn << 2];
ll fa[maxn << 2];
void build(ll i, ll l, ll r)
{
p[i].l = l; p[i].r = r;
p[i].cs = 0;
if (l == r)
{
//cout<<99<<endl;
fa[l] = i;
return;
}
build(i << 1, l, (l + r) >> 1);
build(i << 1 | 1, (l + r >> 1) + 1, r);
}
void upd(ll i, ll x)
{
if (p[i].l == p[i].r)
{
p[i].cs++;
//cout<<p[i].cs<<endl;
return;
}
ll mid = (p[i].l + p[i].r) >> 1;
ll i1 = i << 1;
ll i2 = i << 1 | 1;
if (x <= mid)
upd(i1, x);
if (x >= mid + 1)
upd(i2, x);
p[i].cs = p[i1].cs + p[i2].cs;
//cout<<p[i].cs<<endl;
}
void dt(ll i, ll x)
{
if (p[i].l == p[i].r)
{
p[i].cs--;
//cout<<p[i].cs<<endl;
return;
}
ll mid = (p[i].l + p[i].r) >> 1;
ll i1 = i << 1;
ll i2 = i << 1 | 1;
if (x <= mid)
dt(i1, x);
if (x >= mid + 1)
dt(i2, x);
p[i].cs = p[i1].cs + p[i2].cs;
}
ll query(ll i, ll l, ll r)
{
ll ans = 0;
if (l == p[i].l && p[i].r == r)
{
ans += p[i].cs;
return ans;
}
ll i1 = i << 1;
ll i2 = i << 1 | 1;
if (l <= p[i1].r)
{
if (r <= p[i1].r)
{
ans += query(i1, l, r);
}
else
ans += query(i1, l, p[i1].r);
}
if (r >= p[i2].l)
{
if (l >= p[i2].l)
ans += query(i2, l, r);
else
ans += query(i2, p[i2].l, r);
}
return ans;
}
ll sa(ll i, ll k, ll l, ll r)
{
if (l == r)
{
return l;
}
ll ans = 0;
ll i1 = i << 1, i2 = i << 1 | 1;
if (k <= p[i1].cs)
{
ans = sa(i1, k, l, p[i1].r);
}
else
ans = sa(i2, k - p[i1].cs, p[i2].l, r);
return ans;
}
ll a[500005];
ll b[500005];
map<ll, ll>q;
set<ll>f;
int main()
{
fio();
ll t;
cin >> t;
while (t--)
{
q.clear();
f.clear();
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
a[i] -= i;
f.insert(a[i]);
}
ll cnt = 0;
for (auto j : f)
{
cnt++;
q[j] = cnt;
b[cnt] = j;
}
deque<ll>co;
build(1, 1, cnt);
ll sz = 0;
ll ans = 0;
ll op;
ll an = 1;
for (ll i = 1; i <= n; i++)
{
if (co.empty())
{
co.push_back(a[i]);
upd(1, q[a[i]]);
sz++;
op = b[sa(1, (sz + 1) / 2, 1, cnt)];
ans = 0;
}
else
{
co.push_back(a[i]);
ans += abs(a[i] - op);
upd(1, q[a[i]]);
sz++;
ll mid = b[sa(1, (sz + 1) / 2, 1, cnt)];
if (mid > op)
{
ans += ((sz - 1) / 2) * abs(op - mid);
ans -= (sz - ((sz - 1) / 2)) * abs(op - mid);
}
else if (mid < op)
{
ans -= ((sz + 1) / 2) * abs(op - mid);
ans += (sz - (sz + 1) / 2) * abs(op - mid);
}
while (!co.empty() && ans > m)
{
op = mid;
ans -= abs(co.front() - mid);
dt(1, q[(ll)co.front()]);
sz--;
mid = b[sa(1, (sz + 1) / 2, 1, cnt)];
if (mid > op)
{
ans -= ((sz + 1) / 2) * abs(op - mid);
ans += (sz - (sz + 1) / 2) * abs(op - mid);
}
op = mid;
co.pop_front();
}
op = mid;
an = max(an, (ll)co.size());
}
}
cout << an << endl;
}
}