NOIP2011 提高组合集「建议收藏」

NOIP2011 提高组合集「建议收藏」NOIP2011提高组合集D1T1铺地毯模拟,题目让你干啥你就干啥#include<iostream>#include<cstdio>usingnamespacestd;intx[100010],y[100010],dx[100010],dy[100010];intmain(){intn;…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

NOIP 2011 提高组合集

D1 T1 铺地毯

模拟,题目让你干啥你就干啥

#include <iostream>
#include <cstdio>
using namespace std;
int x[100010],y[100010],dx[100010],dy[100010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d%d",&x[i],&y[i],&dx[i],&dy[i]);
    int a,b;
    scanf("%d%d",&a,&b);
    int r=-1;
    for(int i=1;i<=n;i++)
    {
        if(a>=x[i]&&a<=x[i]+dx[i]&&b>=y[i]&&b<=y[i]+dy[i]) r=i;
    }
    printf("%d\n",r);
    return 0;
} 

D1 T2 选择客栈

做的时候好像麻烦了。我的做法是对于一个可以当接头地点的店,考虑它的贡献。为了避免算重,我们令它是左端点往右走的第一个满足条件的店。说是第一个满足条件,但是不一定非要在这里吃。

然后根据这个节点的往右走第一个不满足的,乘以右边的所有点,更新答案。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010 
#define M 60
using namespace std;
typedef long long ll;
int a[N],b[N],f[N][M];
int main()
{
    int n,k,p; cin >> n >> k >> p ;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for(int i=n;i>=0;i--)
    {
        for(int j=0;j<k;j++)
        {
            f[i][j]=f[i+1][j];
            if(a[i]==j&&i) f[i][j]++;
        }
    }
    // for(int i=1;i<=n;i++) printf("%d %d\n",f[i][0],f[i][1]);
    int bfr=0; ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(b[i]>p) continue;
        for(int j=0;j<k;j++)
        {
            ans+=1ll*(f[bfr+1][j]-f[i+1][j])*f[i+1][j];
            // ans+=(f[bfr+1][j]-f[i][j]);
        }
        ans+=f[bfr+1][a[i]]-f[i][a[i]];
        bfr=i;
    }
    printf("%lld\n",ans); return 0;
}

D1 T3 Mayan游戏

挖坑代填

D2 T1 计算系数

知道二项式定理这题是sb题。

#include <bits/stdc++.h>
#define mod 10007 
using namespace std;
typedef long long ll;
ll quick_power(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
ll before[1010];
int main()
{
    before[0]=1;
    for(ll i=1;i<=1000;i++)
    {
        before[i]=before[i-1]*i%mod;
    }
    ll a,b,k,n,m;
    cin >> a >> b >> k >> n >> m ;
    // a%=mod,b%=mod;
    printf("%lld\n",quick_power(a,n)%mod*quick_power(b,m)%mod*before[k]%mod
        *(quick_power(before[n],mod-2)%mod*quick_power(before[k-n],mod-2)%mod)%mod);
}

D2 T2 聪明的质检员

考虑二分,然后直接暴力枚举验证即可,时间复杂度为O(logn(n+m))。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010 	
using namespace std; typedef long long ll; int n,m; ll S;
int f[N]; ll g[N]; ll L[N],R[N],w[N],v[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
ll rd() {ll x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
ll check(int x)
{
    f[0]=0,g[0]=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1]; g[i]=g[i-1];
        if(w[i]>=x) f[i]++,g[i]+=v[i];
    }
    ll ans=0;
    for(int i=1;i<=m;i++) ans+=1ll*(g[R[i]]-g[L[i]-1])*(f[R[i]]-f[L[i]-1]);
    return ans;
}
int main()
{
    n=rd(),m=rd(),S=rd(); ll maxn=0; for(int i=1;i<=n;i++) w[i]=rd(),v[i]=rd(),maxn=max(maxn,v[i]);
    for(int i=1;i<=m;i++) L[i]=rd(),R[i]=rd();
    ll l=0,r=maxn+1; ll minn=1000000000000000000ll;
    while(l<r)
    {
        int mid=(l+r)>>1;
        ll now=check(mid); minn=min(minn,abs(now-S));
        if(now<S) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",minn);
return 0;
}

D2 T3 观光公交

我们考虑每一个加速器的利与弊即可。如果到达了之后还是需要等,我们减少了以等的那个节点为终点的乘客的时间。如果到达了直接走,我们节省了所有人的时间。所以我们可以贪心地做这个事情。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20010 
using namespace std;
struct node
{
    int start,arrive,target;
}a[N];
int n,m,K,ans;
int f[N],Time[N],g[N],dist[N],sum[N];
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<n;i++)
        scanf("%d",&dist[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].arrive,&a[i].start,&a[i].target);
        f[a[i].start]=max(f[a[i].start],a[i].arrive);
        sum[a[i].target]++;
    }
    for(int i=2;i<=n;i++)
        sum[i]+=sum[i-1];

    Time[1]=0;
    for(int i=2;i<=n;i++)
        Time[i]=max(Time[i-1],f[i-1])+dist[i-1];
    for(int i=1;i<=m;i++)
        ans+=Time[a[i].target]-a[i].arrive;
    while(K)
    {
        g[n]=n;
        g[n-1]=n;
        for(int i=n-2;i;i--)
        {
            if(Time[i+1]<=f[i+1])
                g[i]=i+1;
            else g[i]=g[i+1];
        }
        int Max=0,j;
        for(int i=1;i<=n;i++)
            if(sum[g[i]]-sum[i]>Max&&dist[i]>0)
                Max=sum[g[i]]-sum[i],j=i;
        if(!Max) break;
        ans-=Max;
        dist[j]--;
        K--;
        Time[1]=0;
        for(int i=2;i<=n;i++)
            Time[i]=max(Time[i-1],f[i-1])+dist[i-1];
    }
    cout << ans << endl ;
    return 0;
}

转载于:https://www.cnblogs.com/ShuraK/p/9589056.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/189873.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Intellij Idea 主题下载(Eclectide Monokai)

    Intellij Idea 主题下载(Eclectide Monokai)从国外大神的博客上找的一个很棒的主题EclectideMonoka,感觉是在Durcula上做了很多优化,是黑色主题的升级版,通过一周的使用感觉非常爽,对方法、变量的高亮以及选中的显示等等色彩搭配挺好,分享一下

  • 解决VMware虚拟机桥接模式无法上网「建议收藏」

    解决VMware虚拟机桥接模式无法上网「建议收藏」步骤1:查看本地以太网属性是否安装VMwareBridgeProtocol控制面板>>网络和Internet>>网络连接>>以太网右键属性>>查看是否有安装VMwareBridgeProtocol步骤2:查看VMware虚拟网络编辑器的VMnet0桥接模式设置编辑>>虚拟网络编辑器>>桥接模式>&…

  • emwin 汉字_emwin 弹出效果

    emwin 汉字_emwin 弹出效果emWin—显示汉字最近接触了emWin,需要做一个简单的界面,尝试在基于stm32f429的触摸屏上显示汉字,根据例程里面的操作,字库取模得到了C文件,添加到keil工程里面,最后在触摸屏上却没有显示任何汉字,对于emWin界面的程序结构一脸懵,最后发现有些小细节没有注意。1.字库取模①首先创建一个.txt文本文档,把需要显示的汉字添加进去,然后选择另存。②打开软件FontCvt,生成…

    2022年10月14日
  • redis scan命令_redis 查询命令

    redis scan命令_redis 查询命令我们可能会遇到需要运行的某些命令在godis中不存在的情况,这个时候我们可以使用其原生的方式运行命令,为了方便使用,封装了一个方法,用于简化这个过程。需要注意的是,执行命令的返回结果返回的是interface{},需要对其进行解析成可读的实体结构。传递的参数logger是用来打印日志的://RunRedisCmd运行redis命令funcRunRedisCmd(redis*godis.Redis,logger*log.Logger,cmdstring,args…string)

  • SQL Server 2008 R2 详细安装图文教程

    SQL Server 2008 R2 详细安装图文教程SQLServer2008R2安装教程1、打开安装包,点击setup.exe2、选择左侧列表中的“安装”。3、点击“全新安装或向现有安装添加功能”。4、检测完成点击确定。5、选择版本和密钥,然后下一步。(因为有版权要求,在这不能给安装密钥,需要安装密钥的请私信博主)6、选择“我接受许可条款”。点击下一步7、点击“安装”。8、…

  • resnet源码pytorch_pytorch yolov3训练自己的数据集

    resnet源码pytorch_pytorch yolov3训练自己的数据集书上的,很抽象fromtorchimportnnfromtorch.nnimportfunctionalasFimportosimporttorchvisionclassResidualBlock(nn.Module):def__init__(self,inchannel,outchannel,stride=1,shortcut=None…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号