首页 > 其他分享 >2024ICPC南京部分题解

2024ICPC南京部分题解

时间：2024-11-16 18:58:06浏览次数：1  
标签：单元格 2024ICPC 题解 ll 南京 leq ans include mod

Left Shifting 3

题面：
给定一个长度为 \(n\) 的字符串 \(S = s_0s_1 \cdots s_{n-1}\)，你可以将 \(S\) 向左移动最多 \(k\) 次（包括零次）。计算在操作后字符串中包含的“nanjing”子字符串的最大数量。
更正式地说，让 \(f(S, d)\) 成为将 \(S\) 向左移动 \(d\) 次得到的字符串。也就是说，

\[f(S, d) = s_{(d+0) \mod n} s_{(d+1) \mod n} \cdots s_{(d+n-1) \mod n}. \]

让

\[g(f(S, d), l, r) = s_{(d+l) \mod n} s_{(d+l+1) \mod n} \cdots s_{(d+r) \mod n}. \]

让 \(h(d)\) 成为整数对 \((l, r)\) 的数量，使得 \(0 \leq l \leq r < n\) 并且 \(g(f(S, d), l, r) = \text{"nanjing"}\)。找到一个整数 \(d\)，使得 \(0 \leq d \leq k\) 来最大化 \(h(d)\) 并输出这个最大化的值。
输入：
有多个测试用例。输入的第一行包含一个整数 \(T\)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 \(n\) 和 \(k\)（\(1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 10^9\)），表示字符串的长度和你最多可以执行的左移次数。

第二行包含一个长度为 \(n\) 的字符串 \(s_0s_1 \cdots s_{n-1}\)。该字符串由小写英文字母组成。

保证所有测试用例的 \(n\) 之和不会超过 \(5 \times 10^5\)。
输出：
对于每个测试用例，输出一行包含一个整数，表示字符串中包含的“nanjing”子字符串的最大数量。
样例：
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
——————
2
1
3
0
思路：不管k多大，循环位移最多也就min(n+n,n+m)次，于是考虑n倍增暴力，然后写个前缀和，对于超出n的位置选择pre[i]-pre[n-i]最大值即可,m+n之后不要遍历了

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                     long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
ll ans = 1;
while (y)
{
if (y & 1)
{
ans = ans % mod * (x % mod) % mod;
}
x = x % mod * (x % mod) % mod;
y >>= 1;
}
return ans % mod % mod;
}
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 pre[650000];
int main()
{
	fio();
	ll t;
	cin>>t;
	while(t--)
	{
		ll n,m;
		cin>>n>>m;
		string f;
		cin>>f;
		f+=f;
		f='0'+f;
		m=min(m,n);
		ll ans=0;
		//cout<<n+m<<endl;
		for(ll i=1;i<=n+m;i++)
		{	
			pre[i]=0;
			pre[i]=max(pre[i],pre[i-1]);
			if(i+7-1<=n+m)
			{
			string k=f.substr(i,7);
			if(k=="nanjing")
			{
				pre[i]++;
			}
			//cout<<i
			}
			if(i>=n)
			ans=max(ans,pre[i]-pre[i-n]);
		}
		cout<<ans<<endl;
	}
}

J.Social Media

题面：
在一个社交媒体平台上，用户可以在其他人的帖子下留言来表达他们的想法。然而，这些评论并不是每个人都能看到的。具体来说，对于用户 $ C $ 要看到用户 $ A $ 在用户 $ B $ 的帖子下的评论，他/她必须同时与 $A $ 和 $ B $ 成为朋友。如果一个用户在他/她自己的帖子下留言，他/她所有的朋友都可以看到这条评论。

作为这个平台上的一个活跃用户，你想要看到尽可能多的评论。平台上有 $ k $个用户（不包括你），编号从 1 到 $ k $。平台上也有 $ m $ 条评论，但你可能无法看到所有评论，因为你只有 $n $ 个朋友。由于你需要参加2024年ICPC亚洲南京区域赛，你没有时间交太多新朋友。如果你在平台上最多交两个新朋友，你最多能看到多少条评论？
输入：
有多个测试用例。输入的第一行包含一个整数 \(T\)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 \(n, m, k \left(1 \leq n \leq k \leq 2 \times 10^{5}, 1 \leq m \leq 2 \times 10^{5}\right)\)，表示你的朋友数量、评论数量和平台上的用户数量（不包括你自己）。

第二行包含 \(n\) 个不同的整数 \(f_1, f_2, \cdots, f_n \left(1 \leq f_i \leq k\right)\)，表示你在平台上的朋友。

在接下来的 \(m\) 行中，第 \(i\) 行包含两个整数 \(a_i\) 和 \(b_i \left(1 \leq a_i, b_i \leq k\right)\)，表示用户 \(a_i\) 在用户 \(b_i\) 的帖子下写的评论。

保证所有测试用例的 \(k\) 之和以及 \(m\) 之和都不会超过 \(2 \times 10^{5}\)。
输出：
对于每个测试用例，输出一行包含一个整数，表示如果你在平台上最多交两个新朋友，你可以看到的评论的最大数量。
样例：
5
4 12 7
5 7 3 6
3 6
2 2
1 4
2 4
1 3
7 6
4 1
5 4
1 1
1 1
2 1
3 7
2 7 6
2 4
1 2
3 2
2 5
5 4
2 6
4 6
2 6
1 1 2
1
1 2
2 1 2
1 2
1 2
2 1 100
24 11
11 24
——————
9
5
1
1
1

思路：对于两个要选择的朋友，无非就是给出的连边出现过的，要么就是都没出现的，
后续单纯说连是指连了现在朋友的无关系人员
如果连边出现过，就考虑选择连，连，不连，不连，连，不连，三种情况
如果不连，不连，直接map找到最大值
如果连，不连，则直接用标记找一个连了的，然后另一个没连过的，算他俩的连边和自连边和连现有朋友的最大值
如果连，连，考虑现有连边，自环连边，还有两者连边即可
如果连边没出现过，就只要选择连边数最大的两个与现有朋友连过且不是现有朋友的人员

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                     long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
ll ans = 1;
while (y)
{
if (y & 1)
{
ans = ans % mod * (x % mod) % mod;
}
x = x % mod * (x % mod) % mod;
y >>= 1;
}
return ans % mod % mod;
}
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);
}
struct s
{
ll x,y;
}p[650000];
int main()
{
	fio();
	ll t;
	cin>>t;
	while(t--)
	{
		ll n,m,k;
		cin>>n>>m>>k;
		map<ll,bool>q;
		map<ll,ll>f1,f3,f4;
		map<pair<ll,ll>,ll>o,op;
		for(ll i=1;i<=n;i++)
		{
			ll x;
			cin>>x;
			q[x]=1;
		}
		ll ans=0;
		ll cnt=0;
		for(ll i=1;i<=m;i++)
		{
			ll x,y;
			cin>>x>>y;
			if(q[x]&&q[y])
			{
				ans++;
				continue;
			}
			else 
			{
				cnt++;
				if(x>y)swap(x,y);
				p[cnt].x=x,p[cnt].y=y;
				if(q[x])f1[y]=1,f3[y]++;//标记有联系过朋友
				if(q[y])f1[x]=1,f3[x]++;
				if(x==y)
				{
					f4[x]++;
				}
				else 
				o[{x,y}]++;
			}
		}
		ll an=0;
		priority_queue<ll>cf;
		map<ll,ll>jl;
		for(ll i=1;i<=cnt;i++)
		{
			if(q[p[i].x]==0&&q[p[i].y]==0&&p[i].x!=p[i].y)
			{
			if(f1[p[i].x]&&f1[p[i].y]==0)
			{
				an=max(an,ans+f3[p[i].x]+f4[p[i].x]+o[{p[i].x,p[i].y}]+f4[p[i].y]);
			}
			else if(f1[p[i].x]==0&&f1[p[i].y])
			{
				an=max(an,ans+f3[p[i].y]+f4[p[i].x]+o[{p[i].x,p[i].y}]+f4[p[i].y]);
			}
			else if(f1[p[i].x]&&f1[p[i].y])
			{		
				an=max(an,ans+f4[p[i].x]+f4[p[i].y]+f3[p[i].x]+f3[p[i].y]+o[{p[i].x,p[i].y}]);	
			}
			else 
			{
				an=max(an,o[{p[i].x,p[i].y}]+ans+f4[p[i].x]+f4[p[i].y]);
			}
			}
			else 
			{
			if(q[p[i].x]==0&&jl[p[i].x]==0)
			{
			cf.push(f3[p[i].x]+f4[p[i].x]);
			jl[p[i].x]=1;
			}
			if(q[p[i].y]==0&&jl[p[i].y]==0)
			{
			cf.push(f3[p[i].y]+f4[p[i].y]);
			jl[p[i].y]=1;
			}
			}
			an=max(an,o[{p[i].x,p[i].y}]);
		}
		ll ko=0;
		ll gs=2;
		//cout<<f3[4]<<endl;
		while(!cf.empty())
		{
			gs--;
			ko+=cf.top();
			cf.pop();
			if(gs==0)
			break;
		}
		an=max(an,ko+ans);
		cout<<an<<endl;
	}
}

K.Strips

题面：
有 $ w$ 个单元格排列成一行，从左到右编号为 1 到 $ w $。在这些单元格中，有 $n \(个是红色的，\) m $ 个是黑色的，剩下的 $ w-n-m $ 个单元格是白色的。

你需要用一些条带覆盖所有的红色单元格。每个条带必须覆盖 $ k $ 个连续的单元格。找到一种方法来覆盖所有红色单元格，同时满足以下所有约束条件：

  • 每个红色单元格都被条带覆盖。
  • 没有黑色单元格被条带覆盖。
  • 没有两个条带覆盖同一个单元格。也就是说，每个单元格最多被一个条带覆盖。
  • 使用的条带数量尽可能少。
    输入：
    有多个测试用例。输入的第一行包含一个整数 \(T\)，表示测试用例的数量。对于每个测试用例：

第一行包含四个整数 \(n, m, k\) 和 \(w\)（\(1 \leq n, m \leq 10^5, 1 \leq k \leq w \leq 10^9, n + m \leq w\)），表示红色单元格的数量、黑色单元格的数量、每个条带的长度和总单元格数。

第二行包含 \(n\) 个整数 \(a_1, a_2, \cdots, a_n\)（\(1 \leq a_i \leq w\)），表示单元格 \(a_i\) 是红色的。

第三行包含 \(m\) 个整数 \(b_1, b_2, \cdots, b_m\)（\(1 \leq b_i \leq w\)），表示单元格 \(b_i\) 是黑色的。
保证给定的 \((n+m)\) 个单元格是不同的。还保证所有测试用例的 \(n\) 之和以及 \(m\) 之和都不会超过 \(2 \times 10^5\)。
输出：
对于每个测试用例：
如果可能在满足所有约束条件的情况下覆盖所有红色单元格，首先输出一行包含一个整数 \(c\)，表示使用的条带数量最少。然后输出另一行包含 \(c\) 个整数 \(l_1, l_2, \cdots, l_c\)（\(1 \leq l_i \leq w - k + 1\)），用空格分隔，其中 \(l_i\) 是第 \(i\) 条带覆盖的最左边的单元格。如果有多个有效答案，你可以输出其中任何一个。
如果无法做到这一点，只需输出一行 -1。
样例：
4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2
——————
4
6 2 14 9
-1
2
1 4
-1
思路：当没有限制时，其实最优解就是能以某点作为最左端进行覆盖就是最好的，能覆盖就覆盖于是这题加了限制，就是在最优秀的情况下往左移动知道限制满足为止，
如果最后不满足，则返回-1.没有思路时，还是得从根本出发。

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                     long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
		{
			ans = ans % mod * (x % mod) % mod;
		}
		x = x % mod * (x % mod) % mod;
		y >>= 1;
	}
	return ans % mod % mod;
}
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[450000];
ll b[450000];
vector<ll> ans;
ll d[450000];
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--)
	{
		ans.clear();
		ll n, m, k, w;
		cin >> n >> m >> k >> w;
		for (ll i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		for (ll i = 1; i <= m; i++)cin >> b[i];
		b[m + 1] = w + 1;
		a[n+1]=9999999999999999;
		b[0] = 0;
		sort(a + 1, a + 1 + n);
		sort(b + 1, b + 1 + m);
		ll l,r;
		ll cnt=1;
		ll pd=0;
		for(ll i=0;i<=m;i++)
		{
			l=r=cnt;
			if(cnt==n+1)break;
			if(b[i+1]<a[r])continue;
			while(a[cnt]>=b[i]&&a[cnt]<=b[i+1])
			{
				r=cnt;
				cnt++;
			}
			ll op=0;
			for(ll j=l;j<=r;j++)
			{
				if(j==l)
				{
					op++;
					d[op]=a[j];
				}
				else 
				{
					if(a[j]<=d[op]+k-1)continue;
					else 
					{
						op++;
						d[op]=a[j];
					}
				}
			}
			d[op+1]=b[i+1];
			//cout<<b[i+1]<<endl;
			for(ll j=op;j>=1;j--)
			{
				if(d[j]+k-1>=d[j+1])
				{
					ll u=d[j+1]-(k-1)-1;
					d[j]=u;
				}
				else 
				continue;
			}
			//cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<endl;
			//cout<<cnt<<endl;
			if(d[1]<=b[i])
			{
				pd=1;
				break;
			}
			else 
			{
				for(ll j=1;j<=op;j++)ans.push_back(d[j]);
			}
		}
		if(pd)
		cout<<-1<<endl;
		else 
		{
			cout<<ans.size()<<endl;
			for(auto j:ans)
			cout<<j<<" ";
			cout<<endl;
		}
	}
}

标签：单元格,2024ICPC,题解,ll,南京,leq,ans,include,mod
From： https://www.cnblogs.com/cjcf/p/18549684

相关文章

  • NOIP集训 P4137 Rmq Problem / mex 题解
    前置指使：可持久化线段树题解：P4137RmqProblem/mex有一个长度为\(n\)的数组\(\{a_1,a_2,...,a_n\}\)。\(m\)次询问，每次询问一个区间内最小没有出现过的自然数。Input第一行，两个正整数\(n,m\)。第二行，\(n\)个非负整数\(a_1,a_2,...,a_n\)。接下来\(m\)行，每......
  • 蓝桥杯模拟赛（第一期）个人题解&感想
    林专大一牲第一次写blog，更新较慢，写的不好的地方请见谅（好多题目忘记了题号and暂时没有题目要求的内容…后面会补充的！）本次带来的是蓝桥杯模拟赛第一期的个人题解（笨人水平较低，大家可以在评论区指出错误/讨论更优解~）大多题我是用c++写的，但也掺了几道c，为以后全面用c++打比赛作过......
  • AI｜经常崩溃的问题解决
    AdobeIllustratorCrashes网络上大部分说法都是重装AI，兼容性问题，管理员权限或者是版本不对，经测试均无效，甚至出现重装系统这种离谱的办法，正确的解决办法是把首选项的性能里的GPU取消勾选，或者再把电脑的虚拟内存扩大即可。 Step1：打开首选项 Step2：取消勾选GPU性能......
  • CF987 Div2 F 题解
    阶段1考虑我们每次随机删除两个然后询问，若中位数为\(\frac{n}{2},\frac{n}{2}+1\)称被删除的两个为基准数，用\(v_1,v_2\)代表。每次询问得到解的概率约为\(\frac{1}{2}\)。发现基准数一定一个\(<\frac{n}{2}\)一个\(>\frac{n}{2}+1\)，且对于一次四个数的询问\(x......
  • [AGC018C] Coins 题解
    先全部选\(a_i\)，假设\(b_i=b_i-a_i,c_i=c_i-a_i\)。那么题目转化为选\(y\)个\(b\)和\(z\)个\(c\)使得答案最大。会发现若\(i\)位置选的\(b\)，\(j\)位置选的\(c\)，那么需要满足\(b_i-c_i>b_j-c_j\)。我们按上述条件排序，这样一定是在左边选\(b\)，右边选\(c\)。那......
  • 题解：ABC013D 阿弥陀
    先考虑\(D=1\)，明显可以\(O(M)\)模拟预处理出在最上面的每个位置往下走会走到什么位置，之后每次就可以\(O(1)\)查询了。当\(D>1\)时，可以依赖预处理的数据每次\(O(D)\)暴力查询。又注意到每次对所有位置进行的变换操作是一样的，可以倍增后用类似快速幂的方法优化到\(O(\log......
  • CF2031D 题解
    原题链接最后悔的一集，感觉D\(<\)everything。考虑由确定的点推出其他点的答案，发现最高点的答案是确定的，设其位置为\(x\)。然后根据题目定义，发现可以分成\([1,x-1],[x,n]\)两个区间，\([x,n]\)答案均为\(h_x\)。对于\([1,x-1]\)区间，我们找到第一个\(>[x,n]\)区间最小......
  • 读数据质量管理：数据可靠性与数据质量问题解决之道05数据标准化
    1. 批处理1.1. 批处理在一段时间内收集数据，然后将大量数据“批处理”在离散的数据包中1.2. 直到20世纪10年代中期，批处理都是处理分析型数据最常用的方法1.3. 批处理比流处理要便宜得多，即使是对时间要求最苛刻的处理需求也足以满足1.4. 批处理是经过时间考验的标准，并且仍......
  • POI 四题题解
    P3434[POI2006]KRA-TheDisks考场上不知道在想什么，把\(O(n)\)正解改成\(O(n\mathrm{log}n)\)的了。关于\(O(n\mathrm{log}n)\)做法很多，我只讲我的。直接二分盘子会在哪里卡住，二分范围是\(1\simlst\)。\(lst\)表示上一个盘子卡住的位置。\(\mathrm{Code}\)#includ......
  • CF1909F1 Small Permutation Problem (Easy Version) 题解
    CF1909F1SmallPermutationProblem(EasyVersion)题解直接莽做显然不好统计。考虑统计每一次\(i\)的变化有多少种方案数来匹配，也就是对\(a\)数组差分。考虑到对于\(a_i\)，只有\([1,i]\)里的数会对\(a_i\)有影响。注意到\(p\)形成一个排列，于是我们不妨考虑此时\(p......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99