首页 > 其他分享 >11.13

11.13

时间：2023-11-13 19:48:51浏览次数：40  
标签：ch int 11.13 back while define getchar

T1

很有意思的贪心。

显然只有四种情况：\(a\) 为 \(1/2\)，\(b\) 为 \(1/2\)。

那么为这四种情况分别记录一个 \(vector\)。

我们记录 \(suma\) 为 \(a\) 的总和，\(sumb\) 为 \(b\) 的总和。

那么显然我们需要让这个分配方式达到 \(suma/2\) 和 \(sumb/2\)。

考虑贪心，先将两个都卡在同一起跑线上，然后用 \(11\) 或者 \(22\) 或者 \(12+21\) 操作来贪心即可。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , m , a[N] , b[N] , flag , ans[N];

vector<int> cnt11 , cnt12 , cnt21 , cnt22;

signed main ()
{
	freopen ( "slauqe.in" , "r" , stdin );
	freopen ( "slauqe.out" , "w" , stdout );
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    int T = read();
    while ( T -- )
    {
        int flag = 1;
        cnt11.clear() , cnt12.clear() , cnt21.clear() , cnt22.clear();
        memset ( ans , 0 , sizeof ans );
		n = read();
        int suma = 0 , sumb = 0;
		for ( int i = 1 ; i <= n ; i ++ ) suma += ( a[i] = read() );
		for ( int i = 1 ; i <= n ; i ++ ) sumb += ( b[i] = read() );
        for ( int i = 1 ; i <= n ; i ++ )
        {
            if ( a[i] == 1 && b[i] == 2 ) cnt12.eb(i);
            if ( a[i] == 2 && b[i] == 1 ) cnt21.eb(i);
            if ( a[i] == 1 && b[i] == 1 ) cnt11.eb(i);
            if ( a[i] == 2 && b[i] == 2 ) cnt22.eb(i);
        }

        if ( suma % 2 || sumb % 2 ) { cout << -1 << endl; continue; }

        int dec = abs ( suma / 2 - sumb / 2 );
        int need = min ( suma , sumb ) / 2;

        if ( suma < sumb ) { for ( int i = 1 ; i <= dec ; i ++ ) ans[cnt12.back()] = 1 , cnt12.pb() , -- need; } //需要12
        else { for ( int i = 1 ; i <= dec ; i ++ ) ans[cnt21.back()] = 1 , cnt21.pb() , -- need; }//需要21

        int lst = need;
        while ( need )
        {
            if ( need <= cnt11.size() ) { for ( int i = 0 ; i < need ; i ++ ) ans[cnt11[i]] = 1; break; }
            else if ( need % 2 == 0 && need <= cnt22.size() * 2 ) { for ( int i = 0 ; i < need / 2 ; i ++ ) ans[cnt22[i]] = 1; break; }
            else 
            {
                if ( need >= 3 && cnt12.size() && cnt21.size() )
                {
                    ans[cnt12.back()] = 1 , cnt12.pb();
                    ans[cnt21.back()] = 1 , cnt21.pb();
                    need -= 3;
                }
                else if ( cnt11.size() ) ans[cnt11.back()] = 1 , cnt11.pb() , -- need;
                else if ( cnt22.size() && need % 2 == 0 ) ans[cnt22.back()] = 1 , cnt22.pb() , need -= 2;
            }
            if ( need == lst ) { flag = 0 , cout << -1 << endl; break; }
            lst = need;
        }
        if ( !flag ) continue;
        for ( int i = 1 ; i <= n ; i ++ ) cout << ans[i] << ' ';
        cout << endl;
    }
    return 0;
}

T2

结论题。

\(5pts\ O(n^3)\) 暴力：枚举子段，判断有几次必须改。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = 300 + 5;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}


int n , temp[N] , a[N] , ans , tempb[N];

vector<int> lsh;

signed main ()
{
	freopen ( "sort.in" , "r" , stdin );
	freopen ( "sort.out" , "w" , stdout );
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read();
    for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
    for ( int l = 1 ; l <= n ; l ++ )
    	for ( int r = l + 1 ; r <= n ; r ++ )
    	{
    		int cnt = 0 , suma = 0 , sumb = 0;
			for ( int i = l ; i <= r ; i ++ ) temp[i] = a[i];
            sort ( temp + l , temp + r + 1 );
            for ( int i = l ; i <= r ; i ++ )
            {
                suma += a[i] , sumb += temp[i];
                if ( suma != sumb || a[i] != temp[i] ) ++ cnt;
            }
            ans += cnt;
		}
	cout << ans << endl;	
	return 0;
}

\(20pts\ O(n^2logn)\)：

对于一个点，预处理最远的逆序对，记录在数组中，每次二分查找

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = 5e3 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}


int n , lst[N][N] , a[N] , cnt[N] , ans;

struct Tree
{
	struct node { int sum , add; } t[N<<2];
	inl void up ( int p ) { t[p].sum = t[ls].sum + t[rs].sum; }
	inl void pushdown ( int p , int l , int r , int val ) { t[p].sum = ( r - l + 1 ) * val , t[p].add = val; }
	inl void down ( int p , int l , int r ) { if ( t[p].add ) pushdown ( lson , t[p].add ) , pushdown ( rson , t[p].add ) , t[p].add = 0; }
	void build ( int p , int l , int r )
    {
        t[p].sum = t[p].add = 0;
        if ( l == r ) return;
        build ( lson ) , build ( rson ) , up(p);
    }
    void upd ( int p , int l , int r , int x , int y , int val )
	{
        if ( x > y ) return;
		if ( x <= l && r <= y ) return pushdown ( p , l , r , val );
		down ( p , l , r );
		if ( x <= mid ) upd ( lson , x , y , val );
		if ( mid + 1 <= y ) upd ( rson , x , y , val );
		up(p);
	}
	int query ( int p , int l , int r , int x , int y )
	{
		if ( x <= l && r <= y ) return t[p].sum;
		down ( p , l , r );
		int res = 0;
		if ( x <= mid ) res += query ( lson , x , y );
		if ( mid + 1 <= y ) res += query ( rson , x , y );
		return res;
	}
}T;

int solve ( int x , int y )
{
    if ( upper_bound ( lst[y] + 1 , lst[y] + cnt[y] + 1 , x , greater<int>() ) - lst[y] - 1 == 0 ) return inf;
    int pos = lst[y][upper_bound ( lst[y] + 1 , lst[y] + cnt[y] + 1 , x , greater<int>() ) - lst[y] - 1];
    return pos;
}

signed main ()
{
	freopen ( "sort.in" , "r" , stdin );
	freopen ( "sort.out" , "w" , stdout );
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read();
    for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
    for ( int i = 1 ; i <= n ; i ++ )
    {
        int tot = 0;
        for ( int j = i - 1 ; j ; j -- ) if ( a[j] > a[i] ) lst[i][++tot] = j;
        cnt[i] = tot;
    }
    for ( int i = 1 ; i <= n ; i ++ )
    {
        // memset ( T.t , 0 , sizeof T.t );
        T.build ( 1 , 1 , n );
        for ( int j = i + 1 ; j <= n ; j ++ )
        {
            int lstt = solve ( i , j );
            // cout << i << ' ' << j << ' ' << lstt << endl;
            T.upd ( 1 , 1 , n , lstt , j , 1 );
            ans += T.query ( 1 , 1 , n , i , j );
        }
    }
    cout << ans << endl;
	return 0;
}

\(50pts O(nlogn)\)：

一个结论：

\(100pts\) 是单调栈，不想补了。

T3

搜罢。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int N = 1e6 + 5;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , T , seed1 , seed2 , mod , lst , ans , buc[N] , res , x[N] , y[N];

vector<int> temp;

void solve ( int lim , int stp )
{
	if ( stp == lim + 1 )
	{
		int ret = 0;
		for ( int i = 1 ; i <= lim ; i ++ ) buc[temp[i]] ^= 1;
		for ( int i = 1 ; i <= 1e6 ; i ++ ) if ( !buc[i] ) { ret = i; break; }
		for ( int i = 1 ; i <= lim ; i ++ ) buc[temp[i]] = 0;
		res = max ( res , ret );
		return;
	}
	temp.eb(x[stp]) , solve ( lim , stp + 1 ) , temp.pb();
	temp.eb(y[stp]) , solve ( lim , stp + 1 ) , temp.pb();
}

signed main ()
{
	freopen ( "mex.in" , "r" , stdin );
	freopen ( "mex.out" , "w" , stdout );
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read() , T = read() , seed1 = read() , seed2 = read() , mod = read();
    for ( int i = 1 ; i <= n ; i ++ )
    {
		if ( i <= T ) x[i] = read() , y[i] = read();
		else x[i] = ( ans * i ^ seed1 ) % mod + 1 , y[i] = ( ans * i ^ seed2 ) % mod + 1;
		res = 0;
		temp.eb(0) , solve(i,1) , temp.pb();
		ans ^= ( res * i );
	}
	cout << ans << endl; 
	return 0;
}

T4

对于 \(\le 100\) 的点可以模拟。

如果再大一点，我们可以开一个 \(sum_{i,j}\) 数组表示 \(1-i\) 之间值为 \(j\) 的个数，那么我们枚举 \(i,j\)，用前缀和统计合法的 \(k\) 的个数即可。

对于第二个 \(sub\)，我们可以只开 \(6\) 的第二维。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = 5e4 + 5;
const int maxn = 5e4;
const int mod = 1e9 + 7;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , m , a[N] , lstans;

namespace sub1
{
    void main()
    {
        for ( int i = 1 , l , r ; i <= m ; i ++ )
        {
            int ll = ( read() + lstans ) % n + 1 , rr = ( read() + lstans ) % n + 1;
            l = min ( ll , rr ) , r = max ( ll , rr );
            int res = 0;
            for ( int j = l ; j <= r ; j ++ )
                for ( int k = l ; k <= r ; k ++ )
                    for ( int p = l ; p <= r ; p ++ )
                        res += ( a[j] < a[k] && a[j] * a[j] + a[k] * a[k] == a[p] * a[p] );
            cout << ( lstans = res ) << endl;	
        }    
    }
}

namespace sub2
{
    const int M = 1e3 + 5;
    int sum[M][N];
    void main()
    {
        for ( int i = 1 ; i <= n ; i ++ ) ++ sum[i][a[i]];
        for ( int i = 1 ; i <= n ; i ++ )
            for ( int j = 1 ; j <= maxn ; j ++ )
                sum[i][j] += sum[i-1][j];
        for ( int i = 1 , l , r ; i <= m ; i ++ )
        {
            int ll = ( read() + lstans ) % n + 1 , rr = ( read() + lstans ) % n + 1;
            l = min ( ll , rr ) , r = max ( ll , rr );
            int res = 0;
            for ( int j = l ; j <= r ; j ++ )
                for ( int k = l ; k <= r ; k ++ )  
                    if ( a[j] < a[k] )
                    {
                        int summ = a[j] * a[j] + a[k] * a[k];
                        int temp = sqrt(summ);
                        if ( temp * temp != summ || temp > maxn ) continue;
                        res += sum[r][temp] - sum[l-1][temp];
                    }
            cout << ( lstans = res ) << endl;	
        }    
    }
}

namespace sub3
{
    const int M = 5e4 + 5;
    int sum[M][6];
    void main()
    {
        for ( int i = 1 ; i <= n ; i ++ ) ++ sum[i][a[i]];
        for ( int i = 1 ; i <= n ; i ++ )
            for ( int j = 3 ; j <= 5 ; j ++ )
                sum[i][j] += sum[i-1][j];
        for ( int i = 1 , l , r ; i <= m ; i ++ )
        {
            int ll = ( read() + lstans ) % n + 1 , rr = ( read() + lstans ) % n + 1;
            l = min ( ll , rr ) , r = max ( ll , rr );
            int res = ( sum[r][3] - sum[l-1][3] ) * ( sum[r][4] - sum[l-1][4] ) * ( sum[r][5] - sum[l-1][5] );
            cout << ( lstans = res ) << endl;	
        }    
    }
}


signed main ()
{
	freopen ( "avidity.in" , "r" , stdin );
	freopen ( "avidity.out" , "w" , stdout );
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read() , m = read();
    for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
    // if ( n <= 100 ) sub1::main();
    if ( n <= 1000 ) sub2::main();
    else sub3::main();
    return 0;
}

标签：ch,int,11.13,back,while,define,getchar
From： https://www.cnblogs.com/Echo-Long/p/17829940.html

相关文章

  • 11.13每日总结
    今天完成了软件射进和人机交互的部分实验，主要进行了话题的总结，对我们的话题大学生日常消费的调查进行了总结，对照片进行了汇总并且生成了相应的图表。 ......
  • 11.13周一分级测试反思
    这次分级考试没有做好，一共A，B，C，D四个等级，只做到了c等级，B等级的选课的业务逻辑没有想出来，感觉还是经验不太足，现在反思一下造成这种情况的原因。先说上一周做了什么吧，上周就是发了期末试题后，回来尝试看了看，但是第一步就出错了，springboot工程崩了，在一直在找问题，大概陆陆续续找了一天，终......
  • 11.13日记
    默认情况下，Azure机器学习笔记本中提供了无服务器Spark计算。若要在笔记本中访问它，请从“计算”选择菜单的“Azure机器学习无服务器Spark”下选择“无服务器Spark计算”。笔记本UI还为无服务器Spark计算提供了Spark会话配置选项。配置Spark会话：   选择屏幕顶......
  • 2023.11.13 ~ 2023.11.19
    需要知识点以及学习连接：b站视频：前缀和差分本周题目：1、前缀和【模板题】2、前缀和【例题1】3、二维前缀和【模板题】4、差分【模板题】5、差分【例题1】......
  • 11.13
    今天上java课写了一个选课系统的增删改查，开始很快地写完了学生增加，老师增加和课程增加，还是比较熟练的，随后便是信息的修改，这个也比较熟练，不一会儿就完成了，但难在选课的逻辑上，我尝试去做查询浏览，发现了一个空指针的问题，不知道怎么解决，非常难受，回来尝试重写一遍，问题才迎刃而解......
  • 11.13
    上周还是松懈了，上周周五，周六尝试着写了一下发的上次的期末考试题，实现了不同用户的登录这次课堂测试题目没有实现选课功能，我没有想好怎么统计选课信息，要在同一行的同一对象中持续添加内容，统计选课的所有学生，还要统计学生所选的所有课程，还没想好怎么实现这周尝试一下先将表中的选......
  • 11.13（周一）总结——选课系统个人总结
    今天做的选题系统主要是实现多表的增删改查，但是选课系统本身我目前无法实现。我在三个表的构建中有一个小时思路非常混乱，以后应该先理出角色和整体的思路再开始写，还有要注意文件的命名，因为如果一旦出现错误复盘是非常费力的。还有就是敲代码的速度太慢，无法适应期末的代码量......
  • 云原生周刊：KubeSphere 3.4.1 发布 | 2023.11.13
    开源项目推荐InspektorGadgetInspektorGadget是一组用于调试和检查Kubernetes资源与应用程序的工具（或小工具）。它在Kubernetes集群中管理eBPF程序的打包、部署和执行，包括许多基于BCC工具的程序，以及一些专为在InspektorGadget中使用而开发的程序。它能自动将低级内......
  • 2023.11.13
    最唐的一集。A已知质数\(P=10^{18}+31\)的一个原根为\(g=42\)，给出\(A\)数组满足\(\displaystyleA_i=\begin{cases}795484359100928850&i=0\\\log_gA_{i-1}\bmodP&i>0\end{cases}\)，多次询问\(A_x\)的值。\(1\leT\le10\)，\(0\lex\le10^5\)。input：......
  • 11.13周一黄金行情走势空头为主，反弹继续空，空，空，空
     黄金受周五黑天鹅单边下跌的影响，行情一度跌破1945去到了下方1942低点，虽然随后美盘十一点的数据有利多影响，但这波数据影响也只是给到了我们短线一个再度反弹做空的机会，而反弹走完后行情便再度从上方1945附近开始逐步走跌，最低也是再度触及了下方1932关口才有所企稳！  那么随......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99