Petrozavodsk Winter 2023. Day 1 部分题解

这篇具有很好参考价值的文章主要介绍了Petrozavodsk Winter 2023. Day 1 部分题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:整场的题目质量比较高,虽然之前做过一部分题,但还是被薄纱了

Changing the Sequences

大意:
给定两个数组a,b,长度都为n,元素都介于1-m之间

定义一次操作如下:

构造一个1-m的排列p,对于对于a中的每一个元素,,得到a'

只进行一次该操作,要求使a'与b的元素不相同的位置尽可能少。并求出满足条件的字典序最小的a'

思路:

显然一次操作的本质是构造一个a到a'的单射。我们可以直接考虑映射的值。将ai与对应的bi连边,表示如果ai的映射是bi,可以造成一个贡献。我们希望最终的贡献尽可能多。显然边的权值可以累加。

所以本质上我们就是在一个二分图上寻找匹配,使得匹配边的权值之和尽可能大。也就是最大权匹配问题。如果不考虑字典序最小的话,我们可以直接用KM来解决这个问题。时间复杂度就是m^3

现在想想如何让字典序最小。说来可以,这其实是一种不算罕见的套路,但是赛时我们队还是全体宕机,但事后看看,并没有想象中的那么不可做。

显然字典序最小的前提是保持权值和最大,然后我们去修改可以连边,使得a数组中靠前的数字尽可能去匹配尽可能小的数字。为了做到这一点,我们先将a数组的元素按位置先后从小到大赋值(因为其本身的元素大小并没有什么用,我们关心的只是元素的位置)。

然后无脑跑一遍KM,得到最大的匹配权值和ans。然后我们尝试修改匹配方案。

外层遍历更新后的a数组,内层遍历映射的域,分别记为i,j。尝试将i的映射变成j,我们需要验证i->j的权值贡献加上图的其他部分的贡献与ans相同。那么将i连向其他点的权值置为0,再将其他点连向j的权值置为0,重新跑一遍KM,加上i到j的权值贡献,即可。如果和与ans相同的话,代表这个匹配是可以的。这里有贪心的成分在,但是因为我们是要字典序最小,前缀越小约好,所以可以贪心。匹配成功后,我们就将两个点从图中去除即可。否则恢复成原来的状态。

code文章来源地址https://www.toymoban.com/news/detail-533818.html

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int INF=0x3f3f3f3f;
const int N=1e5+10;

int n,m,match[N],pre[N];
bool vis[N];
int favor[70][70];
int val1[N],val2[N],slack[N];
ll a[N],b[N];
ll mp[N],cn;
ll To[70];
ll Pre[70][70];
ll change[70];
ll VIS[70];

void bfs(int p)
{
    memset(pre,0,sizeof pre);
    memset(slack,INF,sizeof slack);

    match[0]=p;

    int x=0,nex=0;
    do{
        vis[x]=true;

        int y=match[x],d=INF;

        // 瀵逛簬褰撳墠鑺傜偣y锛宐fs鏈夎繛杈圭殑涓嬩竴鐐?
        for(int i=1;i<=m;i++)
        {
            if(!vis[i])
            {
                if(slack[i]>val1[y]+val2[i]-favor[y][i])
                {
                    slack[i]=val1[y]+val2[i]-favor[y][i];
                    pre[i]=x;
                }
                if(slack[i]<d)
                {
                    d=slack[i];
                    nex=i;
                }
            }
        }

        for(int i=0;i<=m;i++)
        {
            if(vis[i])
                val1[match[i]]-=d,val2[i]+=d;
            else
                slack[i]-=d;
        }

        x=nex;

    }while(match[x]);

    while(x)
    {
        match[x]=match[pre[x]];
        x=pre[x];
    }
}

ll KM()
{
    memset(match,0,sizeof match);
    memset(val1,0,sizeof val1);
    memset(val2,0,sizeof val2);
    for(int i=1;i<=m;i++)
    {
        memset(vis,false,sizeof vis);
        bfs(i);
    }
    ll ans=0;
    for(int i=1;i<=m;++i) ans+=favor[match[i]][i];
    	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
		for(int i=1;i<=n;++i) cin>>b[i];

	for(int i=1;i<=n;++i)
	{
		if(!mp[a[i]]) mp[a[i]]=++cn;
		a[i]=mp[a[i]];
	}

	for(int i=1;i<=n;++i)
	{
		favor[a[i]][b[i]]++;
	}
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j) Pre[i][j]=favor[i][j];//原始数组
	}

	ll ans=KM();//全局最优解

	ll sum=0;
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(VIS[j]) continue;
			ll th_val=favor[i][j];
			for(int s=1;s<=m;++s)
			{
				favor[i][s]=0;
				favor[s][j]=0;//除去
			}
			if(th_val+sum+KM()==ans)//代表匹配成功,我们修改它
			{
				VIS[j]=1;
				change[i]=j;
				sum+=th_val;//sum记录之前已经匹配过的映射的权值贡献和
				break;
			}
			for(int s=1;s<=m;++s)
			{
				if(s>=i) favor[s][j]=Pre[s][j];//前面都是已匹配过的点
				if(VIS[s]) continue;//已经连接过
				favor[i][s]=Pre[i][s];
			}

		}
	}
	for(int i=1;i<=n;++i) cout<<change[a[i]]<<' ';

	return 0;
}

Determine The Fluctuation Bonus

大意:

给定n个人,每一个人有一个初始分数为0.q次操作,每次操作给定id,a,第id个人加上a分。每次操作之后所有人按分数重新排序,获得排名变化的绝对值的贡献。

求q次操作之后每一个人的贡献。

思路:

看着难,实际也没那么不可做,还是太怂了

每一个人的分数可以分成两个部分:自己操作带来的贡献,以及别人操作对自己带来的贡献。第一个值其实比较好维护,我们只需要记录每一个人的分数,然后每一次操作的时候维护一下排名,贡献就是排名的变化了,具体实现用一个树状数组T1来维护分数。第二个部分可以用另一个树状数组T2维护。每一次操作之后,分数从pre变成了now,那么只有分数区间在[pre,now-1]之间的人才会获得贡献,并且贡献为1,简单做一个差分即可。

最后一个问题就是如何将两者相加。让第二个树状数组T2记录每一个分数累计获得的贡献。每次操作的时候,对于id,我们然其贡献加上T2(pre),再减去T2(now),即可。因为id之前一直在pre的位置,所以加上这个位置带来的贡献。但是下一次又轮到id操作的时候,它并不是从一开始就待在当前的now这个位置的,所以我们先提前减去T2(now),下一次就可以放心加上对应的值了,实现起来也比较容易。

同时数据值域比较大,我们还要提前离线下来把数据离散化。

写起来有点绕,细节比较多。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) x&(-x)
#define endl '\n'
const ll N=2e5+10;
const ll M=2e5;
struct Tree
{
	ll tr[N];
	void add(ll x,ll y)
	{
		while(x<=M)
		{
			tr[x]+=y;
			x+=low(x);
		}
	}
	ll sum(ll x)
	{
		ll ans=0;
		while(x)
		{
			ans+=tr[x];
			x-=low(x);
		}
		return ans;
	}
	ll Gt_sum(ll l,ll r)
	{
		return sum(r)-sum(l-1);
	}
	void upd(ll l,ll r,ll val)
	{
		add(l,val);add(r+1,-val);
	}
}T1,T2;
ll n,q;
map<ll,ll> mp;
struct ty
{
	ll id,val;
}mas[N];
ll pos[N];
set<ll> st;
int idx=0;
ll ans[N];
void solve()
{
	cin>>n>>q;
	st.insert(0);
	for(int i=1;i<=q;++i)
	{
		cin>>mas[i].id>>mas[i].val;
		st.insert(pos[mas[i].id]);
		pos[mas[i].id]+=mas[i].val;
		st.insert(pos[mas[i].id]);
	}
	for(auto s:st) mp[s]=++idx;
	for(int i=0;i<=n;++i) pos[i]=0;

	// for(auto s:st) cout<<s<<" ";
	// 	cout<<endl;

	T2.add(mp[0],n);
	for(int i=1;i<=q;++i)
	{
		ll id=mas[i].id;ll val=mas[i].val;
		ll pre_pos=mp[pos[id]],now_pos=mp[pos[id]+val];
		pos[id]+=val;

		ll pre_lnk=1+T2.Gt_sum(pre_pos+1,M);
		// T2.upd(pre_pos,pre_pos,-1);T2.upd(now_pos,now_pos,1);
		T2.add(pre_pos,-1);T2.add(now_pos,1);
		ll now_lnk=1+T2.Gt_sum(now_pos+1,M);
		// cout<<id<<" "<<pre_lnk<<' '<<now_lnk<<endl;

		ans[id]+=abs(pre_lnk-now_lnk);
		ans[id]+=T1.sum(pre_pos);
		ll mi=min(pre_pos,now_pos);ll ma=max(pre_pos,now_pos)-1;
		T1.upd(mi,ma,1);
		ans[id]-=T1.sum(now_pos);
	}
	// for(int i=1;i<=n;++i) cout<<ans[i]<<" ";
	// 	cout<<endl;
	for(int i=1;i<=n;++i)
	{
		cout<<ans[i]+T1.sum(mp[pos[i]])<<endl;
	}

}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

到了这里,关于Petrozavodsk Winter 2023. Day 1 部分题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 湘大 XTU OJ 1308 比赛 题解:循环结束的临界点+朴素模拟

    比赛 有 n个人要进行比赛 ,比赛规则如下: 假设每轮比赛的人是m,取 最大的k , k=2^t 且k≤m。 这k个人每2人举行一场比赛 ,胜利者进入一下轮,失败者被淘汰。 余下的m-k个人,不进行比赛,直接进入下一轮 直到决出冠军,比赛结束 。 比如有5个人参加比赛,第一轮举办

    2024年02月13日
    浏览(41)
  • 【超好懂的比赛题解】2021 年四川省大学生程序设计竞赛

    title : 2021 年四川省大学生程序设计竞赛 date : 2022-7-18 tags : ACM,练习记录 author : Linno 题目链接:https://codeforces.com/gym/103117 进度:11/13 切题顺序:AKMBDHLJ IF赛后补了,CG没看 A. Chuanpai 给定正整数 k,问有多少正整数对 (x, y) 满足 x + y = k 且 1 ≤ x ≤ y ≤ 6。 x 和 y 的可行范围很小,

    2024年02月05日
    浏览(43)
  • 2023年高教社杯全国大学生数学建模竞赛-【比赛规则篇】比赛规则及比赛指导

    目录 前言 前辈分享的国赛获奖经验  多看历年的竞赛题 集训时长 模拟题量

    2024年02月07日
    浏览(46)
  • 部分回溯法题解

    中 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n = 3 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2: 输入:n = 1 输出:[“()”] 如果是左括号直接添加 如果是右括号不能超过已经添加的

    2024年02月20日
    浏览(26)
  • Python头歌集合(部分参考题解)

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 提示:这里是本文要记录的大概内容: 头歌实践教学平台,是国内广泛使用的在线实践教学服务平台与创新环境,尤其为高校和企业的实践与创新能力提升作出了贡献。这个平台集成了多种工具,如实

    2024年02月04日
    浏览(38)
  • NewStarCTF week2 部分题解

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、Word-For-You(2 Gen) 二、IncludeOne 三、UnserializeOne 四、ezAPI 五、 Yesec no drumsticks 2 六、Coldwinds\\\'s Desktop 七、qsdz\\\'s girlfriend 2 八、Affine(放射加密) 九、unusual_base 十、人类的本质 十一、EzRabin 提示

    2024年02月06日
    浏览(42)
  • 2023MathorCup数学建模比赛的思路汇总帖

    更新时间【4.13 19:45】ABCD均已更新,选题指导已更新,速看!后续会出各题详细思路及代码! 这里是小云的2023MathorCup数学建模比赛的思路汇总帖,比赛开始后将实时更新~ 竞赛共4道题目(A题、B题、C题和D题) 研究生组同学请从A、B题中任选一个完成答卷; 本科生组及专科

    2023年04月13日
    浏览(55)
  • 【华为OD机试】比赛【2023 B卷|100分】

    【 华为OD机试】-真题 !!点这里!! 【 华为OD机试】真题考点分类 !!点这里  !! 题目描述 一个有N个选手参加比赛,选手编号为1~N(3=N=100),有M(3=M=10)个评委对选手进行打分。 打分规则为每个评委对选手打分,最高分10分,最低分1分。 请计算得分最多的3位选手的编号。

    2024年02月15日
    浏览(37)
  • 2023年网络安全比赛--综合渗透测试(超详细)

    一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 1.扫描目标靶机将靶机开放的所有端口,当作flag提交(例:21,22,23); 2.扫描目标靶机将靶机的http服务版本信息当作flag提交(例:apache 2.3.4); 3.靶机网站存在目录遍历漏洞,请将h

    2024年02月12日
    浏览(47)
  • 2022icpc西安站部分题解-E

    E. Find Maximum 题意:给定边界L和R,算满足的所有的的最大值, 其中满足: 。 题解: 打表发现发现了f(x)与x的三进制有关系,即f(x)等于x三进制的每个数相加,再加上三进制数的有效位数。下图从左向右依次是x,x的三进制,f(x)。 于是便是将问题转变为在区间中找到三进制的每

    2024年02月08日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包