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;
}
- Programming Challenge LS-PC 2023 TFTprogramming challenge ls-pc 2023 ls-pc 2023 programming kingdom ireland programming regional contest 2023 2023 programming acm-icpc american 2023 programming collegiate provincial 2023 programming collegiate contest contest 2023 2022 programming programming languages 2023 top 题解2023 programming collegiate