首页 > 其他分享 >2024 ICPC Asia Taiwan Online Programming Contest题解记录

2024 ICPC Asia Taiwan Online Programming Contest题解记录

时间:2024-10-20 20:12:58浏览次数:5  
标签:Contest 题解 ll Programming long x% ans ans% mod

比赛链接:https://codeforces.com/gym/105383/problem

A. Animal Farm

找个最大pig,然后所有比他小的其他种类生物一直加就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
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;
}
void fio()
{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
}
string f[150000];
ll a[150000];
int main()
{
	fio();
	ll n;
	cin>>n;
	ll cnt=0;
	for(ll i=1;i<=n;i++)
	{
		cin>>f[i]>>a[i];
		if(f[i]=="pig")
		{
			cnt=max(cnt,a[i]);
		}
	}
	ll ans=cnt;
	for(ll i=1;i<=n;i++)
	{
		if(f[i]!="pig"&&a[i]<cnt)
		{
			ans+=a[i];
		}
	}
	cout<<ans<<endl;
}

B. Business Magic

先把负数乘3倍,然后算最大和区间,如果和为正数则这段区间全乘二,且所有负数变成正数;否则所有负数变正数加起来就可以了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
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;
}
void fio()
{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
}
ll a[450000];
ll b[450000];
int main()
{
	fio();
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]<0)b[i]=3*a[i];
		else b[i]=a[i];
	}
	ll l=0,r=0,cnt=0;
	ll f=0;
	deque<ll>q;
	for(ll i=1;i<=n;i++)
	{
		if(q.empty())
		{
			q.push_back(i);
			f+=b[i];
			while(!q.empty()&&f<0)
			{
				f-=b[q.front()];
				q.pop_front();
			}
			if(!q.empty())
			{
				if(f>cnt)
				{
					cnt=f;
					l=i,r=i;
				}
			}
		}
		else 
		{
			q.push_back(i);
			f+=b[i];
			while(!q.empty()&&f<0)
			{
				f-=b[q.front()];
				q.pop_front();
			}
			if(!q.empty())
			{
				if(f>cnt)
				{
					cnt=f;
					l=q.front(),r=q.back();
				}
			}
		}
	}
	//cout<<l<<" "<<r<<endl;
	if(l==0&&r==0)
	{
		ll ans=0;
		for(ll i=1;i<=n;i++)ans+=abs(a[i]);
		cout<<ans<<endl;
	}
	else 
	{
		ll ans=0;
		for(ll i=1;i<=n;i++)
		{
			if(i>=l&&i<=r)
			ans+=a[i]*2;
			else 
			ans+=abs(a[i]);
		}
		cout<<ans<<endl;
	}
}

D. Disbursement on Quarantine Policy

分类讨论即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
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;
}
void fio()
{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
}
ll add(ll x,ll y)
{
	return (x%mod+y%mod)%mod;
}
ll p1=ksm(2,mod-2)%mod;
string f[6000];
ll ans=0;
ll n,m,d1,d2,d3;
ll a[4]={0,1,0,-1};
ll b[4]={1,0,-1,0};
ll c[4]={-1,1,1,-1};
ll d[4]={-1,-1,1,1};
void ck(ll x,ll y)
{
	if(f[x][y]=='V')
	{	
		ans=(ans%mod+d1%mod)%mod;
		return ;
	}
	else if(f[x][y]=='?')
	{
		ll nx;
		ll ny;
		ll pd=0;
		ll pd1=0;
		ll cnt=0;
		ll cnt1=0;
		for(ll i=0;i<=3;i++)
		{
			nx=x+a[i];
			ny=y+b[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m)//四角
			{
				if(f[nx][ny]=='V')pd=1;
				if(f[nx][ny]=='?')cnt++;
			}
		}
		for(ll i=0;i<=3;i++)
		{
			nx=x+c[i];
			ny=y+d[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m)//八角
			{
				if(f[nx][ny]=='V')pd1=1;
				if(f[nx][ny]=='?')cnt1++;
			}
		}
		if(pd)//四角有v
		{
			ll u=(p1*d1)%mod;
			ans=add(ans,u);
			ll k=(p1*d2)%mod;
			ans=add(ans,k);
			return ;
		}
		else if(pd1)//八角
		{
			ans=(ans%mod+p1*d1%mod)%mod;
			ll u=((((1-ksm(p1,cnt)%mod+1000*mod)%mod%mod)*d2%mod)%mod+1000*mod)%mod;
			ll y=(ksm(p1,cnt)%mod*d3%mod)%mod;
			ans=(ans%mod+(p1%mod*((u%mod+y%mod)%mod))%mod)%mod;
		}
		else
		{
			ans=(ans%mod+p1*d1%mod)%mod;
			ll u=(((1-ksm(p1,cnt)%mod+1000*mod)%mod)*d2%mod+1000*mod)%mod;
			ll y=(((1-ksm(p1,cnt1)%mod+1000*mod)%mod)*d3%mod+1000*mod)%mod;
			y=(y%mod*ksm(p1,cnt)%mod)%mod;
			ans=(ans%mod+(p1%mod*((u%mod+y%mod)%mod))%mod)%mod;
		}
		return ;
	}
	else 
	{
		ll nx;
		ll ny;
		ll pd=0;
		ll pd1=0;
		ll cnt=0;
		ll cnt1=0;
		for(ll i=0;i<=3;i++)
		{
			nx=x+a[i];
			ny=y+b[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
			{
				if(f[nx][ny]=='V')pd=1;
				if(f[nx][ny]=='?')cnt++;
			}
		}
		for(ll i=0;i<=3;i++)
		{
			nx=x+c[i];
			ny=y+d[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
			{
				if(f[nx][ny]=='V')pd1=1;
				if(f[nx][ny]=='?')cnt1++;
			}
		}
		if(pd)
		{
			ans=(ans%mod+d2%mod)%mod;
		}
		else if(pd1)
		{
			ll u=(((1-ksm(p1,cnt)%mod+1000*mod)%mod)*d2%mod+1000*mod)%mod;
			ll y=(((ksm(p1,cnt)%mod)%mod)*d3%mod)%mod;
			ans=(ans%mod+(u%mod+y%mod)%mod)%mod;
		}
		else 
		{
				ll u=(((1-ksm(p1,cnt)%mod+1000*mod)%mod)*d2%mod+1000*mod)%mod;
				ll y=(ksm(p1,cnt)%mod*d3%mod)%mod;
				y=(y%mod*((1-ksm(p1,cnt1)+1000*mod)%mod)%mod)%mod;
				ans=(ans%mod+(u%mod+y%mod)%mod)%mod;
		}
		return ;
	}
}
int main()
{
	fio();
	// cout<<p1<<endl;
	cin>>n>>m>>d1>>d2>>d3;
	d1%=mod;
	d2%=mod;
	d3%=mod;
	for(ll i=1;i<=n;i++)cin>>f[i],f[i]='0'+f[i];
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			ck(i,j);
		}
	}
	cout<<ans<<endl;
}

J. Just Round Down

直接long double +long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
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;
}
int main()
{
	long double n;
	cin>>n;
	cout<<(ll)n<<endl; 
}

K. Kingdom's Development Plan

和codeforces div3的一道题很像,于是参考了那个的判环思路,
然后入度+优先队列即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
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;
}
void fio()
{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
}
vector<ll>g[250000];
bool vis[250000];
bool vi[250000];
ll pd=0;
ll l=0;
ll b[2500000];
ll in[2500000];
ll ans1=0;
vector<ll>op;
ll n,m;
void dfs(ll x)
{
	if(vi[x])
	{
		pd=1;
		return ;
	}
	if(vis[x])return;
	vis[x]=1;
	ans1++;
	vi[x]=1;
	for(auto j:g[x])
	{
		dfs(j);
	}
	vi[x]=0;
}
void to()
{
	priority_queue<ll,vector<ll>,greater<ll>>q;
	for(ll i=1;i<=n;i++)
	{
		if(in[i]==0)
		q.push(i);
	}
	while(!q.empty())
	{
		ll j=q.top();
		q.pop();
		for(auto x:g[j])
		{
			in[x]--;
			if(in[x]==0)
			{
				q.push(x);
			}
		}
		op.push_back(j);
	}

}
int main()
{
	fio();
	cin>>n>>m;
	while(m--)
	{
		ll l,r;
		cin>>l>>r;
		g[l].push_back(r);
		in[r]++;
	}
	for(ll i=1;i<=n;i++)
	{
		if(vis[i])continue;
		else if(in[i]==0)
		{
			dfs(i);
		}
	}
	if(pd||ans1!=n)
	cout<<"IMPOSSIBLE"<<endl;
	else 
	{
		to();
		for(auto j:op)
		{
			cout<<j<<" ";
		}
		cout<<endl;
	}
}

标签:Contest,题解,ll,Programming,long,x%,ans,ans%,mod
From: https://www.cnblogs.com/cjcf/p/18487773

相关文章

  • P10233 [yLCPC2024] A. dx 分计算 题解
    题目大意:题目传送门共\(T\)组测试数据,每组数据给定一个字符串\(s\)和\(Q\)次询问,按照特定的赋值方式,每次询问\(l\)到\(r\)间按这样的赋值方式的总和是多少。赋值方式如下:P可得3分p可得2分G可得1分其余字符不得分题目分析:前置知识:前缀和。(没有学过的可以先......
  • http://192.168.14.232/contest/59
    A:创历史新低dalao:d<=5,所以一个位置上只能是[i-d,i+d],考虑状压ljx'scode#include<bits/stdc++.h>usingnamespacestd;constintmaxn=505;constintmod=998244353;intread(){ intret=0,f=1;charch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;......
  • 题解:AT_abc376_c [ABC376C] Prepare Another Box
    很好的一道二分答案题。听说CSP考前写tj可以让rp+=inf?注:下文中\(w\)指物品重量序列,\(x\)指箱子容量序列。先问个问题:为什么我上来就敢肯定这是个二分答案题?或者说,单调性在哪儿?非常简单:如果一个盒子的容量越大,能装下的东西就更多(废话)。那么如果\(v\)不够用,可以扩......
  • 【学校训练记录】10月个人训练赛4个人题解
    A:要使s,t相等只要互相删除对方没有的字母即可,即找到a-z字母拥有最少的#include<bits/stdc++.h>#defineendl"\n"#defineintlonglongusingnamespacestd;strings1,s2;inta1[30],a2[30];voidsolve(){ cin>>s1>>s2; for(inti=0;i<s1.size(......
  • 【洛谷 P1116】车厢重组 题解(模拟+冒泡排序)
    车厢重组题目描述在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他......
  • 【洛谷 P1116】车厢重组 题解(模拟+冒泡排序)
    车厢重组题目描述在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他......
  • CF1187E 题解
    Titletranslation给定一棵\(n\)个点的树,初始全是白点。要做\(n\)步操作,每一次选定一个与一个黑点相隔一条边的白点,将它染成黑点,然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点,求可获得的最大权值。Solution如何让这道题秒降绿题呢?先简化一......
  • 题解:AT_abc376_c [ABC376C] Prepare Another Box
    这道题要求把\(a\)数组和\(b\)数组一一匹配,且要求无法匹配的数量最多为一,并且这个无法匹配的元素最小。可以注意到我们把两个数组排序以后一一对应以后如果出现一个无法匹配的元素,那么这一定就是答案。但是如果我们从小到大枚举,会发现最后剩下的元素不一定最小,所以我们选择......
  • Atcoder Beginner Contest 376
    新猫ΛΛ__/(*゚ー゚)/\/| ̄UU ̄|\/||/A.CandyButton\(\text{diff}19\)你按一次按钮就会得到一颗糖,如果这次按按钮和上次得到糖的间隔时间小于\(C\)则不会得到糖,给你若干按按钮的时间,问能得到多少糖intn,c;inta[1000001];signedmain(){cin>>n>>......
  • 【题解】「COCI 2018」Teoretičar
    LinkofThisProblem根据Vizing定理,最小的答案就是二分图的最大度数。同时可以在\(O(nm)\)的时间复杂度内构造出一组解。显然对于这道题我们需要更高效的做法。注意到\(2\)的整数次幂,考虑分治。既然答案跟最大度数有关,如果我们每次能把边集分为两个集合,认为她们的颜色......