首页 > 其他分享 >团队训练记录2024.10.7

团队训练记录2024.10.7

时间:2024-10-07 19:11:27浏览次数:7  
标签:2024.10 训练 ll mid cin ans cs 团队 op

赛时依然和本校强队差两题
比赛链接: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

用权值线段树+离散化实现中位数查找,然后维护一个中位数即可

//不用主席树,用权值线段树+离散化照样可以,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;
	}
}

标签:2024.10,训练,ll,mid,cin,ans,cs,团队,op
From: https://www.cnblogs.com/cjcf/p/18450428

相关文章

  • 2024.10.7 test
    nf#33B有一棵包含\(n\)个节点的有根树,且树的高度不超过\(100\)。每次操作时可以选择一个节点\(u\),使其与父节点断开(如果有),成为一颗新树的根节点,然后删除以节点\(u\)为根的树中的所有叶节点。求删除所有节点所需的最少操作次数和通过最少次操作删除所有节点的方案数。\(n......
  • 团队管理的两大入门心法
    https://www.cnblogs.com/ivan-uno/p/18449607 很久没有更新博客了,最近几年专注于技术团队的管理工作,事情一忙就放松了对自己的要求,那么就从一篇管理心得重新开始吧。团队管理的入门心法,有两个重点,明确管理者的使命和选择合适的管理风格。一.管理者的使命一个团队管理者的......
  • 团队管理的两大入门心法
    很久没有更新博客了,最近几年专注于技术团队的管理工作,事情一忙就放松了对自己的要求,那么就从一篇管理心得重新开始吧。团队管理的入门心法,有两个重点,明确管理者的使命和选择合适的管理风格。一.管理者的使命一个团队管理者的使命是什么?我认为有两点,“达成目标”和“发展成员”......
  • 2024.10.6训练记录
    下午cfA到!B签到题,考场还是写挂了,今天码力差。挂在while动指针的时候没有判右边界,似。唐诗程度不亚于数组开小。C1猜出来结论是第一次出现需要按照一开始的顺序就能过。C2把一开始的排列映射到[1,n]。修改时用set动态维护每个数第一次出现的位置。把第一次出现位置的......
  • Git分支-团队协作以及GitHub操作
    Git分支操作在版本控制过程中,同时推进多个任务==>程序员开发与开发主线并行,互不影响分支底层也是指针的引用hot-fix:相当于若在进行分支合并后程序出现了bug和卡顿等现象,通过热补丁来进行程序的更新,确保程序正常运行常用操作命令命令作用gitbranch分支名创建......
  • 代码随想录算法训练营day7|● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ●
    学习资料:https://programmercarl.com/0015.三数之和.html#其他语言版本学习记录:454.四数相加(hash_dict,前两个数一组遍历a+b,后两个数一组遍历找0-(a+b))点击查看代码classSolution:deffourSumCount(self,nums1:List[int],nums2:List[int],nums3:List[int],nums4:......
  • 代码随想录算法训练营 | 56. 合并区间,738.单调递增的数字
    56.合并区间题目链接:56.合并区间文档讲解︰代码随想录(programmercarl.com)视频讲解︰合并区间日期:2024-10-06想法:重叠区间类似问题Java代码如下:classSolution{publicint[][]merge(int[][]intervals){List<int[]>res=newArrayList<>();Arra......
  • 2024.10 做题记录 /
    CF2004E套用SG函数的结论,我们先打单个游戏的表再异或即可得到答案。首先对于一个大小为\(i\)的堆有\(SG[i]=\text{mex}_{j\boti}\{SG[i-j]\}\),容易暴力dp。intSG[N];intf(intx){ if(SG[x]!=-1)returnSG[x]; if(x==0)returnSG[0]=0; vector<int>g; up(i,1,x......
  • 【CodeForces训练记录】Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final
    赛后反思做红温了,太菜了,每题都需要WA几次才能过,B题看到MEX选择性害怕,时间复杂度又算错了A题每次选择一对\(a_i,a_j\)把均值插入数组最后面,要想结果最大,对于两个数求均值,最后的结果一定是小于等于其中的较大值,我们可以考虑如何最大化最后一次操作,想到将最大值保留在最后再......
  • 10.5组队训练赛-2024CCPC山东省赛
    10.5组队训练赛-2024CCPC山东省赛成绩4排名8(差3题)写在前面Ika是简单题,但是因为a爆longlong一直没有看出来,导致交了很都发。出现的问题就是代码能力太弱,不能保证一遍过。改错的能力也很弱,没有及时发现出错的地方,一直在题意理解和算法方面打转。浪费时间。J题想了......