首页 > 其他分享 >The 2021 ICPC 南京 ACJM

The 2021 ICPC 南京 ACJM

时间：2023-10-04 12:56:26浏览次数：47  
标签：const int ll nullptr cin ICPC 2021 ACJM pre2

The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)

A.Oops, It’s Yesterday Twice More

思路：考虑先把所有袋鼠集中在一起然后再移动。因为有步数限制(\(\le3(n-1)\))。那么分类讨论移动到四个角上，看哪个符号条件的就输出。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,a,b;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>a>>b;
    //LU
    int x = 1,y = 1;
    if((a-x)+(b-y)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"L";
        for(int i = 1;i <= n-1;i++)cout<<"U";
        for(int i = 1;i <= b-y;i++)cout<<"R";
        for(int i = 1;i <= a-x;i++)cout<<"D";
        return 0;
    }
    //RU
    x = 1,y = n;
    if((a-x)+(y-b)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"R";
        for(int i = 1;i <= n-1;i++)cout<<"U";
        for(int i = 1;i <= y-b;i++)cout<<"L";
        for(int i = 1;i <= a-x;i++)cout<<"D";
        return 0;
    }
    //LD
    x = n,y = 1;
    if((x-a)+(b-y)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"L";
        for(int i = 1;i <= n-1;i++)cout<<"D";
        for(int i = 1;i <= b-y;i++)cout<<"R";
        for(int i = 1;i <= x-a;i++)cout<<"U";
        return 0;
    }
    //RD
    x = n,y = n;
    if((x-a)+(y-b)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"R";
        for(int i = 1;i <= n-1;i++)cout<<"D";
        for(int i = 1;i <= y-b;i++)cout<<"L";
        for(int i = 1;i <= x-a;i++)cout<<"U";
        return 0;
    }


    return 0;
}

C. Klee in Solitary Confinement

思路：

做法一：(公式推导)我们考虑枚举众数是谁，然后去写。对于众数是\(x+k\)的情况，只有\(x\)对它有贡献。那么考虑对于一段区间\([L,R]+k\),我们对于众数是\(x\)情况的贡献是什么呢？

![image-20230901231020613](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230901231020613.png)

如上图所示：

为了更快的处理区间问题，我们先预处理出对于某个数\(x+k\)的前缀出现次数\(pre2\)，和\(x\)的前缀出现次数\(pre1\)

那么对于\([L,R]+k\)，对于众数是\(x+k\)的贡献是\(pre2[L-1]+pre2[n]-pre[R]+pre1[R]-pre1[L-1]\)

移向得：\(pre2[n]+(pre1[R]-pre1[L-1])-(pre2[R]-pre2[L-1])\)

因为\(pre2[n]\)是定值，那么我们只需要后面这个东西最大就行了。我们固定左界去枚举右界，取max就是答案。

还有一个问题，如何处理出这个东西？

我们先用\(vector<int>idx[N]\)存下每种值的下标，然后呢，对于众数是\(x+k\)的情况，只有\(x\)是对它有贡献的。我们把\(idx[x]\)和\(idx[x+k]\)取出来，根据下标，把它们排成一排，假设这两组数总共是有\(c\)个，那\(for(1～c)\)对两组数做前缀操作。做完以后还是\(for(1～c)\)去求\(pre2[n]+(pre1[R]-pre1[L-1])-(pre2[R]-pre2[L-1])\)的最大值。

对于时间复杂度：因为每个数\(x\)至多被访问\(2\)次(\(x+k\)和\(x-k\))，那么时间复杂度\(O(2n)\).

注意：下标有负数，我们做个偏移。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e6 + 10,M = 2e6;
vector<int>idx[N];
int pos[N];
int cnt[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k;
    cin>>n>>k;
    ll maxn = -1e9;
    ll res = -1e18;
    for(int i = 1;i <= n; i++)
    {
        ll x;
        cin>>x;
        x += M;
        cnt[x]++;
        if(cnt[x]>res)res = cnt[x];
        maxn = max(maxn,x);
    	idx[x].push_back(i);
    }
   	//cout<<"mx = "<<maxn<<"\n";
  
    
    for(int i = 0;i <= 4e6; i++)
    {
    	int c =  0;
    	int x = i,y = i+k;
    	if(y<0||y>4e6)continue;
    	int sz1 = idx[x].size(),sz2 = idx[y].size();
    	
    	if(y<0||y>4e6||sz1==0||sz2==0)continue;
    	//cout<<"x = "<<x-M<<" y = "<<y-M<<"\n";
    	int cnt1 = 0,cnt2 = 0;
    	while(cnt1 < sz1|| cnt2 < sz2)
    	{
    		if(cnt1 == sz1)
    			pos[idx[y][cnt2]] = ++c,cnt2++;
    		else if(cnt2 == sz2)
    			pos[idx[x][cnt1]] = ++c,cnt1++;
    		else{
    			if(idx[x][cnt1] < idx[y][cnt2])
    				pos[idx[x][cnt1]] = ++c,cnt1++;
    			else pos[idx[y][cnt2]] = ++c,cnt2++;
    		}
    	}
    	// cout<<"pos1 :";
    	// for(int i = 0;i<sz1;i++)
    	// 	cout<<pos[idx[x][i]]<<" ";
    	// cout<<"\n";
    	// cout<<"pos2 :";
    	// for(int i = 0;i<sz2;i++)
    	// 	cout<<pos[idx[y][i]]<<" ";
    	// cout<<"\n";
    	vector<ll>pre1(c+1),pre2(c+1);
    	
    	for(auto j:idx[x])
    		pre1[pos[j]]++;
    	for(auto j:idx[y])
    		pre2[pos[j]]++;
    	for(int i = 1; i <= c; i++)
    		pre1[i] += pre1[i-1],pre2[i] += pre2[i-1];
    	// for(int i = 1;i <= c;i++)
    	// 	cout<<pre1[i]<<" ";
    	// cout<<"\n";
    	// for(int i = 1;i <= c;i++)
    	// 	cout<<pre2[i]<<" ";
    	// cout<<"\n";
    	ll t = 0;
    	for(int i = 1;i <= c; i++)
    	{
    		t += (pre1[i]-pre1[i-1])-(pre2[i]-pre2[i-1]);
    		if(t<0)t = 0;
    		res = max(res,t + pre2[c]);
    	}
    }
    cout<<res<<"\n";
    
    return 0;
}

做法二：

考虑一个区间\(+k\)带来的影响：

对于一个区间原本的数是\(x\)，现在变成了\(x+k\)，原本是\(x-k\)的数现在变成了\(x\)。

如果选择\(x\)是众数，那么对于这个所选区间内\(x\)的贡献是\(-1\),\(x-k\)的贡献是\(+1\)。那么对于给定\(x\)，我们只需要找出最大贡献区间即可。但是如果枚举每个\(a_i\)然后再去扫一遍看贡献肯定超时了，那怎么办呢？当我们枚举到第\(i\)个位置的时候，我们统计\(a_i\)和\(a_i+k\)产生的贡献，也就是说，我们\(for\)一遍相当于枚举了全部的\(a_i\)。

那么如何选区间呢？从开始一直去取，直到某个位置贡献小于0了，那就不要这段了，因为从这段负的继续加不会更优。所以我们把这段区间丢掉，从新开始计算贡献。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e6 + 10,M = 2e6;
vector<int>idx[N];
int ret[N],a[N],pre[N],cnt[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k;
    cin>>n>>k;
    int ans = 0;
    for(int i = 1;i <= n; i++)
    {
        cin>>a[i];
        cnt[a[i]+M]++;
        ans = max(ans,cnt[a[i]+M]);
    }   
    if(k==0){
        cout<<ans<<"\n";
        return 0;
    }

    for(int i = 1;i <= n; i++)
    {
        ret[a[i]+M]--;
        if(ret[a[i]+M]<0)ret[a[i]+M] = 0;
        ret[a[i]+k+M]++;
        ans = max(ans,cnt[a[i]+k+M]+ret[a[i]+k+M]);
    }
    cout<<ans<<"\n";
    return 0;
}

思想：边扫边统计答案，无需先确定区间再去算。

J. Xingqiu's Joke

思路：对于同时\(+1\)和同时\(-1\)的操作，两数的差值的不变的。\(c = abs(a-b)\)。

若\(g|a\)且\(g|c\)那么\(g|abs(a-b)\)。

\(dp[\lbrace a,a+\delta\rbrace]\)表示从\((a,a+\delta)\)得到\(1\)的步数。我们去枚举\(\delta\)的质因数\(g\)。

而\(dp[\lbrace a,a+\delta\rbrace]\)可以由\(dp[\lbrace \lfloor \dfrac{a}{g}\rfloor,\dfrac{\delta}{g}\rbrace]\)和\(dp[\lbrace \lceil \dfrac{a}{g}\rceil,\dfrac{\delta}{g}\rbrace]\)转移得到。我们去记忆化一下就可以写了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll int
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<ll>d;
void div(ll x)
{
    for (ll i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0)
            {
                x = x / i;
                s++;
            }
            d.push_back(i);
        }
    }
    if (x > 1)d.push_back(x);
}
 
map<pair<ll,ll>,ll>dp;
 
ll dfs(ll a,ll c)
{
	if(a==1)return 0;
	if(c==1)return a-1;
	ll &res = dp[{a,c}];
	if(res)return res;
	res = a-1;
	for(auto g : d)
	{
		if(c % g == 0)
		{
			int left = a%g;
			ll t1 = left+1+dfs(a/g,c/g);
			ll t2 = (g-left)+1+dfs(a/g+1,c/g);
			res = min({res,t1,t2});
		}
	}
	return res;
 
}
 
 
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
 
     	ll a,b;
     	cin>>a>>b;
     	d.clear();
     	dp.clear();
     	if(a>b)swap(a,b);
     	ll c = abs(a-b);
     	div(c);
     	// for(auto g : d)
     	// 	cout<<g<<" ";
     	// cout<<"\n";
     	cout<<dfs(a,c)<<"\n";
    }
 
    return 0;
}

M. Windblume Festival

思路：分类讨论。

  1. 有正有负。用负数一直减正数。最后用正数减负数这样最优。结果是\(\sum_{i = 1}^{n}a_i\)
  2. 全正。先变出一个负数之后，变成第一种情况。
  3. 全负。先变出一个正数之后，变成第一种情况。

因为\(2,3\)不知道变哪个，需要\(for\)一遍。

注意：特判\(n=1\)的情况。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int cntn = 0,cntp = 0;
        ll sum = 0;
        for(int i = 0;i < n; i++)
        {
           cin>>a[i];
           sum += abs(a[i]);
           if(a[i]<0)cntn++;
           else if(a[i]>0)cntp++;
        }
        if(n==1)
        {
            cout<<a[0]<<"\n";
            continue;
        }
        ll ans = -1e18;
        if(cntn>0&&cntp>0)
        {
            ans = sum;
        }
        else if(cntn)
        {
            for(int i = 0;i < n; i++)
            {
                if(a[i]-a[(i+1)%n]>=0)
                    ans = max(ans,(a[i]-a[(i+1)%n])+sum+a[i]+a[(i+1)%n]);
            }
        }
        else if(cntp)
        {
            for(int i = 0;i < n; i++)
            {
                if(a[i]-a[(i+1)%n]<=0)
                   ans = max(ans,sum-(a[i]-a[(i+1)%n])-a[i]-a[(i+1)%n]);
            }
        }
        else ans = 0;
        cout<<ans<<"\n";
    }
    return 0;
}

标签：const,int,ll,nullptr,cin,ICPC,2021,ACJM,pre2
From： https://www.cnblogs.com/nannandbk/p/17742147.html

相关文章

  • 2020 ICPC 南京 EFKL
    2020-2021ACM-ICPC,AsiaNanjingRegionalContest(XXIOpenCup,GrandPrixofNanjing)E.EvilCoordinate思路：因为如果给定了起点和初始走法，其实我们的终点是一定确定的。我们不妨让上下左右的连着一块走，那么对于\(RLUD\)一共有\(4!\)种走法(全排列)，我们暴力枚举然后\(ch......
  • The 2022 ICPC 南京 ADG
    The2022ICPCAsiaNanjingRegionalContestA.Stop,YesterdayPleaseNoMore思路：因为袋鼠是同时移动的，所以我们可以不考虑袋鼠怎么动，而去考虑边界怎么动。所以我们先不考虑洞的影响，先确定哪些会因为边界而离开。确定好最终边界，再进行一次模拟，加入有洞的情况，发现洞产生的路径......
  • caxa软件2021下载安装包 安装包下载方式
    CAXA2019电子图板是一款专门给设计工程师们所打造的二维CAD设计软件，该软件类似于AutoCAD这些软件，都是可以用作室内设计。软件不仅仅具有完全的自主知识产权，而且还拥有了超过二十多万的企业用户成功应用，非常稳定可靠，它是百万工程师必备的CAD软件。除此之外，这款软件功能非常强大，不仅......
  • 2023 ICPC 香港
    gym开场发现E是传统数据结构题很高兴，不过先跳了。F知道相邻两段的长度差\(\le1\)，以为最终每段长度只有\(\lfloor\frac{n}{m+1}\rfloor,\lceil\frac{n}{m+1}\rceil\)两种，那就可以DP了，队友签完HA我上去写，呼救两次后WAontest2，gjk说不相邻的两端长度差不一定\(\le1......
  • 20213227《计算机基础与程序设计》第一周学习总结
    作业信息1.作业属于哪个课程：https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP2.这个作业要求在哪里：https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP/homework/127543.作业的目标：快速浏览教材《计算机科学概论》,提出自己不懂或最想解决的问题4.作业正文：第一章......
  • 题解 [CSP-S 2021] 括号序列
    题目链接对于括号题，基本是栈匹配没有匹配的左括号和区间\(dp\)两个方向。这道题括号序列并不确定，只能用区间\(dp\)搞。如果直接设\(f_{l,r}\)表示\(l\simr\)的合法括号序列，那么由区间\(dp\)的套路可知，需要枚举中间点进行合并，那么\(()()()\)的情况就会出问题，原因是......
  • abaqus下载 - abaqus(有限元软件)v2021免费版 安装包下载方式
    Abaqus2019是一款广泛使用的有限元分析软件，它提供了强大的建模和分析工具，可以帮助用户进行各种复杂结构的力学仿真分析。以下是Abaqus2019的主要特点：软件地址：看置顶贴软件特色一、接触和约束1.接触和约束概览2.Abaqus/Standard中的边-边接触二、材料1.材料概览2.并行流变框架(PRF......
  • 2021 CCPC 威海
    gym知乎确定了我先写缺省源，gjk正开，zsy倒开的策略先读了EFGH，发现是概率、博弈、计数，只能做H，感觉我已经到点了。队友签了AJzsy说M是多项式快速幂并准备开冲，看榜发现逆十字6min过了不太对劲，跟gjk讨论了一下还是有了简单做法。gjk又写了D，WA了之后我看了一眼发现求......
  • 20211301 学习笔记4
    学习笔记4教材知识总结7.1文件操作级别文件操作：分为5个级别（从高到低如下）硬件级别：fdisk（硬盘、U盘、sdc盘分区mkfs：格式化磁盘分区，为系统做好准备fsck：检查和维修系统碎片整理：压缩文件系统中的文件操作系统内核中的文件系统函数系统调用I/O库函数用户命令......
  • 2023ICPC网络赛第二场
    2023ICPC网络赛第二场MDirtyWork解题思路:算出解决每道题的时间的期望，升序排序，前缀和累加即可。时间复杂度:\(O(nlogn)\)代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;typedefpair<int,int>pii;#definefi#defineseintn;voidsolv......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99