首页 > 其他分享 >2023 LS-PC Programming Challenge TFT

2023 LS-PC Programming Challenge TFT

时间：2023-08-07 11:57:40浏览次数：47  
标签：shuffle int Challenge Programming PC num maxn using now

2023 LS-PC Programming Challenge TFT

2344 ASCII Area - PCOI Online Judge (pcoij8.ddns.net)

题目大意

求一个封闭区域的面积

做法

我们考虑一行一行看，第一次遇到斜线时标记一下，接下来每一个点都加入答案，等到下一次遇到斜线时为止，再额外加上一

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
char a;
bool vis=false;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a;
			if(vis&&a=='.')ans++;
			else if(!vis&&(a=='/'||a=='\\'))vis=true;
			else if(vis&&(a=='/'||a=='\\'))vis=false,ans++;
		}
	}
	cout<<ans<<endl;
	
	
	return 0;
}

2345 Billboard - PCOI Online Judge (pcoij8.ddns.net)

题目大意

有h个栏，每栏宽度为w，有n个广告，我们要按顺序找到第一个可以放下广告的栏

做法

考虑线段树，线段树内存一段中能放下的最大值

如果左边符合要求，就往左边找，否则向右找

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+5;
int n,w,h,X;
struct Tree{
	int tr[maxn*4];
	void build(int now,int l,int r){
		tr[now]=w;
		if(l==r)return ;
		int mid=(l+r)/2;
		build(now*2,l,mid);
		build(now*2+1,mid+1,r);
		return ;
	}
	int check(int now,int l,int r,int x){
//		cout<<now<<" "<<l<<" "<<r<<" "<<x<<" "<<tr[now]<<endl;
		if(tr[now]<x)return h+1;
		if(l==r){
			tr[now]-=x;
			return l;
		}
		int mid=(l+r)/2;
		int ANS=check(now*2,l,mid,x);
		if(ANS==h+1)ANS=check(now*2+1,mid+1,r,x);
		tr[now]=max(tr[now*2],tr[now*2+1]);
		return ANS;
	}
}T;
int main(){
	cin>>h>>w>>n;
	h=min(n,h);
	T.build(1,1,h);
	for(int i=1;i<=n;i++){
		cin>>X;
		int pos=T.check(1,1,h,X);
		if(pos==h+1)pos=-1;
		cout<<pos<<endl;
	}
	
	
	return 0;
}

2346 Class - PCOI Online Judge (pcoij8.ddns.net)

题目大意

拥挤度为行人数的最大值 与 列人数的最大值 中取最小值

让拥挤度最大

做法

贪心

考虑人都放第一行和第一列，有多随便放

不够的话尽量平均放，第一行和第一列的人数相差不过一

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,r,c;
char a[maxn][maxn];
int main(){
	cin>>n>>r>>c;
	if(n>=min(r,c)*2-1){
		n++;
		for(int i=1;i<=min(r,c);i++){
			n-=2;
			a[1][i]=a[i][1]='#';
		}
		cout<<min(r,c)<<endl;
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				if(a[i][j]=='#')cout<<"#";
				else {
					if(n!=0)n--,cout<<"#";
					else cout<<".";
				}
			}
			cout<<endl;
		}
		return 0;
	}
	else {
		n++;
		cout<<n/2<<endl;
		for(int i=1;i<=n/2;i++){
			a[1][i]='#';
			a[i][1]='#';
		}
		n%=2;
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				if(a[i][j]=='#')cout<<"#";
				else {
					if(n!=0)n--,cout<<"#";
					else cout<<".";
				}
			}
			cout<<endl;
		}
	}
	
	
	return 0;
}

2347 Defence Fortress - PCOI Online Judge (pcoij8.ddns.net)

题目大意

有N段路，如果是奇数长度为\(\frac{i+1}{2}\),如果是偶数长度为\(N+1-\frac{i}{2}\)

Q个询问，找出连续一段使长度为X

做法

我们发现一个奇数后接一个偶数的话，长度必为N+1

我们可以先对X取模

然后我们尝试向左扩一个，向右扩一个，或者两边同时扩一个

最后判断答案是否合法

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,x;
bool check(int num){
	return 1<=num&&num<=n;
}
signed main(){
	cin>>n>>q;
	while(q--){
		cin>>x;
		int NUM=x/(n+1);
		x=x%(n+1);
		if(NUM*2>n){
			cout<<-1<<" "<<-1<<endl;
			continue;
		}
		if(x==0){
			cout<<1<<" "<<NUM*2<<endl;
			continue;
		}
		int ANS1=(n+1-x)*2;
		int ANS2=x*2-1;
		if(check(ANS1)&&check(ANS1+NUM*2))cout<<ANS1<<" "<<ANS1+NUM*2<<endl;
		else if(check(ANS2)&&check(ANS2-NUM*2))cout<<ANS2-NUM*2<<" "<<ANS2<<endl;
		else if(x==NUM&&check(2*x-1+2))cout<<2<<" "<<2*x-1+2<<endl;
		else cout<<-1<<" "<<-1<<endl;
		
	}
	
	
	return 0;
}

2348 Equality Control - PCOI Online Judge (pcoij8.ddns.net)

题目大意

两行代码，比对返回相同结果的概率是否相同

有以下四种操作

  • \([x_1,...,x_n]\) is the constructor for lists. It returns the integers inside the brackets in their given order.
  • concat(<Expr1>,<Expr2>) returns a list of all the integers returned when evaluating the expression <Expr1> followed by all of the integers returned when evaluating <Expr2>.
  • shuffle(<Expr>) returns a list of all the integers returned by <Expr>, rearranged according to a uniformly random permutation, i.e., each permutation of the elements is used with equal probability.
  • sorted(<Expr>) returns a list of all the integers returned by <Expr>, rearranged into non-decreasing order.

对于\(shuffle\)操作

As an example, consider the first expression of Sample Input 1. The two shuffle exressions both take the list [1,2] as input and return one of the lists [1,2] and [2,1], each with probability 0.5 (independently of each other). The outer concat operator takes the two returned lists as its input and returns their concatenation. I.e., it returns one of the lists [1,2,1,2], [1,2,2,1], [2,1,1,2], and [2,1,2,1], each with probability 0.25.

做法

我们发现，如果外面是shuffle操作或者是sorted操作，我们只需要把里面的数收集起来然后排序，我们并不关心里面有什么操作，但对于shuffle我们要打标记

如果是其他两个操作，我们直接往后加就可以了

另外我们发现，如果shuffle操作里面的数都相同，那和没有shuffle一样，我们不用额外打标记

最后我们一个一个数比对，如果上下有其中一个被打了标记，那就绝对不相同，

如果上下都打了标记，而且数字相同，也不意味着相同

比如：

concat(shuffle([1,2,2,3]),shuffle([4,5]))

shuffle([1,2,2,3,4,5])

因此此时我们要比对一下上下同时shuffle了多少数字，如果个数不相同，那上下就不相等

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
string s[3];
int dep[3][maxn],cnt[3],S[3][maxn];
vector<int>q[3][maxn];
bool check_num(int whi,int now){
	return '0'<=s[whi][now]&&s[whi][now]<='9';
} 
int check(int I,int i,int WHI){
	cnt[I]++;
	int lim=dep[I][i];
	bool flag_num=false;
	int last_num=0;
	while(WHI?(i<s[I].size()&&dep[I][i]==lim):(dep[I][i]>=lim)){
		if(check_num(I,i)){
			if(!flag_num)flag_num=true;
			last_num=last_num*10+s[I][i]-'0';
		}
		else{
			if(flag_num){
				flag_num=false;
				q[I][cnt[I]].push_back(last_num);
				last_num=0;
			}
		}
		i++;
	}
	i--;
	return i;
}
signed main(){
	cin>>s[1]>>s[2];
	s[1]=" "+s[1];
	s[2]=" "+s[2];
	for(int I=1;I<=2;I++){
		for(int i=1;i<s[I].size();i++){
			dep[I][i]+=dep[I][i-1];
			if(s[I][i]=='(')dep[I][i]++;
			if(s[I][i]==')')dep[I][i+1]--;
			
		}
		for(int i=1;i<s[I].size();i++){
			if(dep[I][i]==dep[I][i-1]+1){
				if(s[I][i-1]=='e'||s[I][i-1]=='d'){
					bool whi=false;
					if(s[I][i-1]=='d')whi=true;
					i=check(I,i,0);
					sort(q[I][cnt[I]].begin(),q[I][cnt[I]].end());
					if(whi||q[I][cnt[I]][0]==q[I][cnt[I]][q[I][cnt[I]].size()-1]);
					else S[I][cnt[I]]=1;
				}
			}
			else if(check_num(I,i)){
				i=check(I,i,1);
			}
		}
	}
	int st11=1,st12=0;
	int st21=1,st22=0;
	bool Flag=false;
	while(1){
		int num=S[1][st11]+S[2][st21];
		if(num==1||q[1][st11][st12]!=q[2][st21][st22]||num==2&&q[1][st11].size()!=q[2][st21].size())break;
			
		st12++;
		st22++;
		while(st11!=cnt[1]+1&&st12==q[1][st11].size())st11++,st12=0;
		while(st21!=cnt[2]+1&&st22==q[2][st21].size())st21++,st22=0;
		if(st11==cnt[1]+1&&st21==cnt[2]+1){
			Flag=true;
			break;
		}
		if(st11==cnt[1]+1||st21==cnt[2]+1)break;
	}
	if(Flag)cout<<"equal\n";
	else cout<<"not equal\n";
	return 0;
}

2349 Froggy Ford - PCOI Online Judge (pcoij8.ddns.net)

题目大意

青蛙过河，增加一个石头，使单次跳的最大距离最小

做法

先考虑不增加石头，我们使用dij把一块石头向左岸走和向右岸走的最小的最大距离算出来

然后枚举两个点，在中间放石头，更新最小值

在石头和岸边间放石头要特判

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2*1e6+5,maxm=1e3+5;
const double oo=1000000000000;
typedef double db;
const db eps=1e-3;
int n,cnt=0;
db f[maxm][3],W;
bool vis[maxn]={false};
struct edge{
	int fr,to;
	db len;
}w[maxn];
struct node{
	int x,y;
}a[maxm];
struct node2{
	int x;
	double y;
};
priority_queue<node2>q;
const bool operator<(node2 y,node2 x){
	return x.y<y.y;
}
db d[maxm][maxm];
db get_dis(int x,int y)
{
	return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
void dij(int ST){
	memset(vis,false,sizeof vis);
	q.push({ST,0});
	while(!q.empty()){
		int now=q.top().x;
		q.pop();
		vis[now]=true;
//		cout<<now<<" "<<f[now][0]<<endl;
		for(int i=0;i<=n+1;i++){
			if(vis[i])continue;
			if(ST==0){
				if(f[i][0]>max(f[now][0],d[now][i])){
					f[i][0]=max(f[now][0],d[now][i]);
					q.push({i,f[i][0]});
				}
			}
			if(ST==n+1){
				if(f[i][1]>max(f[now][1],d[now][i])){
					f[i][1]=max(f[now][1],d[now][i]);
					q.push({i,f[i][1]});
				}
			}
		}
	}
}
signed main()
{
	cin>>W>>n;
	if(n==0){
		printf("%.4f %.4f\n",W/2,10);
		return 0;
	}
	int st=0;
	int en=n+1;
	for(int i=1;i<=n;i++){
		f[i][0]=oo;
		cin>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			db num=get_dis(i,j);
			d[i][j]=num;
			d[j][i]=num;
		}
	}
	for(int i=1;i<=n;i++){
		d[st][i]=a[i].x;
		d[i][st]=a[i].x;
		d[en][i]=W-a[i].x;
		d[i][en]=W-a[i].x;
	}
	for(int i=0;i<=n+1;i++){
		f[i][1]=oo;
		f[i][0]=oo;
	}
	d[st][en]=W;
	d[en][st]=W;
	f[0][0]=0;
	f[n+1][1]=0;
	dij(st);
	dij(en);
	db minn=1e18,minni=W/2,minnj=0;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
//			printf("%.4f %.4f\n",f[i][0],f[i][1]);
//			cout<<f[i][0]<<" "<<f[i][1]<<endl;
			db NUM=max(max(f[i][0],f[j][1]),d[i][j]/2);
			if(NUM-minn<=eps){
				minn=NUM;
				minni=(a[i].x+a[j].x)*1.0/2;
				minnj=(a[i].y+a[j].y)*1.0/2;
//				minni=i;
//				minnj=j;
			}
		}
	}
//	cout<<endl<<endl;
//	printf("%.4f %.4f\n",minni,minnj);
	for(int i=1;i<=n;i++){
		db NUM=max(f[i][0],(W-a[i].x)*1.0/2);
		if(NUM-minn<=eps){
			minn=NUM;
			minni=(a[i].x+W)*1.0/2;
			minnj=a[i].y*1.0;
		}
		NUM=max(f[i][1],a[i].x*1.0/2);
		if(NUM-minn<=eps){
			minn=NUM;
			minni=a[i].x*1.0/2;
			minnj=a[i].y*1.0;
		}
	}
	printf("%.4f %.4f\n",minni,minnj);
	
	return 0;
}

2350 Glossary Arrangement - PCOI Online Judge (pcoij8.ddns.net)

题目大意

在不超过宽度的情况下，使使用的行数的最大值最小

做法

考虑二分，看一下这个行数能不能符合条件

拿到行数限制之后，我们考虑dp

\(n^2\)dp，过于显然，不多赘述

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e3+5;
int n,num[maxn],f[maxn],w,d[maxn],e[maxn],b[maxn],c[maxn];
string s[maxn];
bool check(int lim){
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++){
		int maxx=0;
		for(int j=i;j>=max(1,i-lim+1);j--){
			maxx=max(maxx,num[j]);
			f[i]=min(f[i],f[j-1]+maxx+1);
		}
	}	
	return f[n]-1<=w;
}
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		num[i]=s[i].size();
	}
	int l=0,r=n;
	while(l+1<r){
		int mid=(l+r)/2;
//		cout<<l<<" "<<r<<" "<<mid<<" ";
		if(check(mid))r=mid;
		else l=mid;
//		cout<<f[n]<<endl;
	}
//	cout<<r<<endl;
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++){
		int maxx=0;
		for(int j=i;j>=max(1,i-r+1);j--){
			maxx=max(maxx,num[j]);
			if(f[i]>f[j-1]+maxx+1){
				f[i]=f[j-1]+maxx+1;
				d[i]=j-1;
				e[i]=maxx;
			}
		}
	}	
//	for(int i=1;i<=n;i++)cout<<d[i]<<" ";cout<<endl;
//	for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
	int now=n;
//	cout<<n<<" ";
	int cnt=1;
	b[1]=n;
	while(d[now]!=0){
		b[++cnt]=d[now];
//		cout<<d[now]<<" ";
		now=d[now];
	}
	d[0]=0;
//	cout<<endl<<endl;
	for(int i=1;i<=cnt;i++)c[i]=b[cnt-i+1];
//	for(int i=1;i<=cnt;i++)cout<<c[i]<<" ";cout<<endl;
	c[0]=0;
	cout<<r<<" "<<cnt<<endl;
	cout<<e[c[1]];for(int i=2;i<=cnt;i++)cout<<" "<<e[c[i]];cout<<endl;
	for(int i=1;i<=r;i++){
		for(int j=0;j<cnt;j++){
			cout<<std::left<<setw(e[c[j+1]]+1);			
			if(c[j]+i>c[j+1])cout<<" ";
			else cout<<s[c[j]+i];
			

		}
		cout<<endl;
	}
	return 0;
}

2351 Holes - PCOI Online Judge (pcoij8.ddns.net)

题目大意

给出洞的个数，输出满足的最小数

做法

0时为1,1时为零，其他情况奇数先填4，剩下都填8

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	if(n==0)cout<<1<<endl;
	else if(n==1)cout<<0<<endl;
	else {
		if(n%2==1)cout<<4;
		for(int i=1;i<=n/2;i++)cout<<8;
		cout<<endl;
	}
	return 0;
}

2353 Interview Question - PCOI Online Judge (pcoij8.ddns.net)

题目大意

每逢a,b的倍数时特殊报数，给出一段报数情况，求a，b

做法

特殊报数时取gcd，如果没取过就是最大值加1

代码

#include<bits/stdc++.h>
using namespace std;
int c,d,a,b;
string s;
int main(){
	cin>>c>>d;
	for(int i=c;i<=d;i++){
		cin>>s;
		if('0'<=s[0]&&s[0]<='9')continue;
		else if(s[0]=='B')b=__gcd(b,i);
		else if(s.size()==4)a=__gcd(a,i);
		else a=__gcd(a,i),b=__gcd(b,i);
	}
	if(a==0)a=d+1;
	if(b==0)b=d+1;
	cout<<a<<" "<<b<<endl;
	return 0;
}

标签：shuffle,int,Challenge,Programming,PC,num,maxn,using,now
From： https://www.cnblogs.com/Ayaka-T/p/17611032.html

相关文章

  • 636-基于FMC的Kintex XCKU060高性能PCIe载板
    一、板卡概述   板卡主控芯片采用Xilinx公司的KintexUltraScale系列FPGAXCKU060-2FFVA1156。板载2组64bit的DDR4SDRAM，每组容量2GB，可稳定运行在2400MT/s。支持PCIEGen3x8模式及一路FMCHPC接口。同时可提供Windows，Linux上位机驱动。 二、主要规格 ● 板载......
  • 611-基于VU9P的2路4Gsps AD 2路5G DA PCIe收发卡
    一、板卡概述    基于XCVU9P的5GspsADDA收发PCIe板卡。该板卡要求符合PCIe3.0标准，包含一片XCVU9P-2FLGA2014I、2组64-bit/8GBDDR4、2路高速AD，2路高速DA，支持外触发，外时钟。板卡工作温度范围0到60℃，板卡设计加工包含散热装置，支持服务器风冷散热。软件包括接口测试软件，......
  • KTU Programming Camp (Day 3)
    A.Queries维护一个序列，要求支持单点修改和查询区间异或和之和线段树对于每一个二进制位单独考虑。考虑第\(b\)位的异或前缀和\(S\)，则区间\([l,r]\)内的异或和为\(S_r\oplusS_{l-1}\)。若结果不为零，则\(S_r\)和\(S_{l-1}\)一个为\(0\)一个为\(1\)。设区......
  • 主成分分析PCA
    主成分分析PCA目录主成分分析PCA简介PCA的具体实施的过程Python代码实现sklearn中PCA实现数据降维并可视化PCA进行图像压缩参考资料简介降维就是一种对高维度特征数据预处理方法。降维是将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的......
  • gRPC Test
    目录简单使用ghzgithub：https://github.com/bojand/ghzghz官方文档：https://ghz.sh/简单使用下载后解压，将目录配置到path上，方便命令调用：ghz--insecure--protoxxx\Hello.proto--callpackage_name.service_name.rpc_method_name-d"{\"name\":\"a\"}"localho......
  • 2022ICPC南京站 B. Ropeway
    也许更好的阅读体验\(\mathcal{Description}\)\(n+2\)个点编号\(0～n+1\)，每个点有点权，要求选若干个点使得总点权最小，其中编号为\(0\)和\(n+1\)的点必须选且点权为\(0\)，同时满足任意两个被选的点之间的距离不超过\(k\)，此外还会给一个\(01\)串，表示\(1～n\)这些点是否为必选的点现在会......
  • 如何通过gRPC传输文件
    在gRPC中，可以通过将文件分割成多个小块，然后使用流式RPC将这些小块发送到服务器来传输文件。以下是一个简单的示例，展示了如何在gRPC中实现文件传输。首先，我们需要定义一个服务来处理文件传输。在.proto文件中，我们可以定义一个UploadFile服务，它接收一个流式的Chunk消息，并返回一个Up......
  • PLC、DCS、SCADA系统通过OPC智能网关与云平台实时通讯
    OPC作为一种工业控制领域常用的标准通信规约，如PLC、DCS、SCADA等工业自动化系统大多提供了基于OPC规约的数据访问接口，通过OPC智能网关即可采集自动化设备系统数据并将数据传输至云端，打通工业系统数据孤岛，实现数据的互联互通，利用云端大数据平台对数据进行智能化运营。物通博联推出的......
  • AP2400 LED照明电源驱动 DC-DC降压恒流IC 过EMC线路图 PCB线路图 车灯摩灯
    产品特点宽输入电压范围：5V～100V可设定电流范围：10mA～6000mA固定工作频率：150KHZ内置抖频电路，降低对其他设备的EMI干扰平均电流模式采样，恒流精度更高0-100%占空比控制，无电流节点跳变输出短路保护过温保护三功能模式：全亮/半亮/爆闪/三功能循环SOP8封装产品描述AP2400是一款PWM工作模......
  • P9369 [ICPC2022 Xi'an R] Tree
    我们可以发现每个点集要么是一个链，要么是不同子树中的许多点。那么显然，如果我们想要取一个链作为集合，那么只有把这个链一直取到叶子才是最优的。那么我们考虑把这棵树做长链剖分，假设我们得到了p条长链，每条长链的长度为lp_i。假设我们一开始全都用第二类集合来划分，那么答案显......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99