Codeforces Round #401 (div.2)

首页 > 代码库 > Codeforces Round #401 (div.2)

2024-09-05 21:14:06 220人阅读

自己的号2000+了....临时找了一个1540的号，和一个大佬@ditoly一起打...

这是大佬↓

技术分享

迟到了一下，过了十分钟才报名.....

A.......

B.你有n个数，对面也有n个数，两两对决！！！

求最多大于对面的数多少场，大等于对面的数多少场。

直接贪心

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
} 
int s[1005],s2[1005];
int n;

int solve(int*a,int*b)
{
    int l1=1,r1=n,l2=1,r2=n;int sum=0;
    while(l1<=r1)
    {
        if(a[l1]>b[l2]) {++l2;++l1;++sum;}
        else if(a[r1]>b[r2]){sum++;--r1;--r2;}
        else {sum+=a[l1]>b[r2];++l1;--r2;}
    }
    return sum;
}

int solve2(int *a,int*b)
{
    int sum=n;int l1=1,r1=n,l2=1,r2=n;
    while(l1<=r1)
    {
        if(a[l1]>=b[l2]) {++l2;++l1;--sum;}
        else if(a[r1]>=b[r2]){sum--;--r1;--r2;}
        else {sum-=(a[l1]>=b[r2]);++l1;--r2;}    
    }
    return sum;
}

int main()
{
   n=read();
   for(int i=1;i<=n;i++)
         s[i]=getchar()-‘0‘;
   getchar();
   for(int i=1;i<=n;i++)
      s2[i]=getchar()-‘0‘;        
   sort(s+1,s+n+1);
   sort(s2+1,s2+n+1);
   printf("%d\n%d",solve2(s2,s),solve(s2,s));
   return 0;
}

给定一个矩阵，每次给一个lr，求第l到第r行有没有一列是不降的

预处理每一个点最上到多少是不降的，直接暴力...

这是ditoly写的

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0;char c;
    while((c=getchar())<‘0‘||c>‘9‘);
    for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘;
    return x;
}
#define MN 100000
#define N 131072
#define INF 0x7FFFFFFF
vector<int> v[MN+5];
vector<pair<int,int> > q[MN+5];
int t[N*2+5],ans[MN+5];
void change(int k,int x){for(t[k+=N]=x;k>>=1;)t[k]=min(t[k<<1],t[(k<<1)+1]);}
int main()
{
    int n,m,k,i,j;
    n=read();m=read();
    for(i=0;i<=m;++i)v[0].push_back(INF);
    for(i=1;i<=n;++i)v[i].push_back(0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)v[i].push_back(read());
    for(k=read(),i=0;i<k;++i)j=read(),q[read()].push_back(make_pair(j,i));
    memset(t,127,sizeof(t));
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)if(v[i][j]<v[i-1][j])change(j,i);
        for(j=0;j<q[i].size();++j)ans[q[i][j].second]=(t[1]<=q[i][j].first);
    }
    for(i=0;i<k;++i)puts(ans[i]?"Yes":"No");
}

给n个字符串，求最少删去多少个字符可以让这些串按照字典序排列。

这个也是ditoly写的。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0;char c;
    while((c=getchar())<‘0‘||c>‘9‘);
    for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘;
    return x;
}
#define MN 100000
#define N 131072
#define INF 0x7FFFFFFF
vector<int> v[MN+5];
vector<pair<int,int> > q[MN+5];
int t[N*2+5],ans[MN+5];
void change(int k,int x){for(t[k+=N]=x;k>>=1;)t[k]=min(t[k<<1],t[(k<<1)+1]);}
int main()
{
    int n,m,k,i,j;
    n=read();m=read();
    for(i=0;i<=m;++i)v[0].push_back(INF);
    for(i=1;i<=n;++i)v[i].push_back(0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)v[i].push_back(read());
    for(k=read(),i=0;i<k;++i)j=read(),q[read()].push_back(make_pair(j,i));
    memset(t,127,sizeof(t));
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)if(v[i][j]<v[i-1][j])change(j,i);
        for(j=0;j<q[i].size();++j)ans[q[i][j].second]=(t[1]<=q[i][j].first);
    }
    for(i=0;i<k;++i)puts(ans[i]?"Yes":"No");
}

n个环形，每个有a,b,h 如果bj<=b[i]&&b[j]>a[i] 那么可以把j叠到i上面求最大的西格玛 h

按照b排序，然后离散a，建线段树，加速dp就可以了。

这个是我写的...

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 262144
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
} 
int n;
struct tower{
    int a,b,h;
}s[500005];
int l[500005];

ll T[2*N+5];

void renew(int x,ll ad)
{
    x+=N;T[x]=max(T[x],ad);
    for(x>>=1;x;x>>=1)
        T[x]=max(T[x<<1],T[(x<<1)+1]);    
}

ll query(int l,int r)
{
    if(r==0) return 0;
    ll sum=0;
    for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1) sum=max(sum,T[l+1]);
        if( r&1) sum=max(sum,T[r-1]);    
    }
    return sum;
}

bool cmp(tower x,tower y)
{
    return x.b>y.b||(x.b==y.b&&x.a>y.a);
}

int main()
{
   n=read();
   for(int i=1;i<=n;i++)
   {
       s[i].a=read();s[i].b=read();
       s[i].h=read();
       l[i<<1]=s[i].a;l[(i<<1)-1]=s[i].b;    
   }
   sort(s+1,s+n+1,cmp);
   sort(l+1,l+n*2+1);
   int j=0;
   for(int i=1;i<=n*2;i++)
      if(l[i]!=l[i-1])
         l[++j]=l[i];
   for(int i=1;i<=n;i++)
   {
        s[i].a=lower_bound(l+1,l+j+1,s[i].a)-l;
        s[i].b=lower_bound(l+1,l+j+1,s[i].b)-l;    
    }
   for(int i=1;i<=n;i++)
   {
        ll x=query(1,s[i].b-1);
        renew(s[i].a,x+(ll)s[i].h);
   }
   printf("%I64d\n",query(1,j));
   return 0;
}

当时的场景还原

我：您切c啊我做一做ab

ditoly：吼吧

我去做a 瞬间卡壳了一下然后打了个表

ditoly：这比赛有毒吧一点都不照顾pascal选手

我：法克我a wa了（然后发现写错了一个字符）

ditoly：你在干什么啊（然后a了c）

我：我a掉b了我d你e吧

ditoly：我d把，我乱写一个

我：我会e了，我去写一写。

（过了一下）：woc 没开ll wa了这不稳健啊

ditoly：你干什么啊我才是稳健选手啊（a了d）

调了调我：貌似a大的排前面啊交不交啊

ditoly：交啊反正都被你弄成这样了（wa了三次惨遭暴d）

我：哇居然pp了中毒啊啊啊

ditoly：哎（叹气）

我：我们去x人吧

ditoly：看了好久没x点啊

我：我学到了很多姿势啊比如贴一个不调用的筛法在上面做模板啊还有 if(a==0) cout<<0; else if(a==1) cout<<1; 之类的姿势啊

ditoly：哈哈哈哈哈哈哈哈

最后：

技术分享

ditoly：哎两个人都打不过别人这rank1是谁啊

同学：学军中学的许先有吧

我：害怕

感想：我好菜啊 ditoly无敌强

Codeforces Round #401 (div.2)

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > Codeforces Round #401 (div.2)

Codeforces Round #401 (div.2)

看完仍有疑问？有类似问题直接问程序猿