[Codeforces #210] Tutorial

摘要:
vis[i])返回量,0;放;forprintf;return0;}问题AB:答案的可行性是单调的。每次判断两部分答案时,$dp[i]$用于表示要删除的$i$的数量$i$必须采用#include 使用namespacestd;类型deflonglongll;typedefpair<int,int>P;组分MAXN=2e3+10;intn,k,l,r,dat[MAXN],dp[MAXN];Boolcheck{intert=n;fordp[i]=i-1;forforifdp[i]=min;forret=min;returns[i]$进行计算。当$t[i]]˃s[i]$时,贡献变为$*$$dp[i][j]$:前一个$i$bit是左端结果为$j$的方案数,它分为$t[i]˃s[i]$$和$t[i][i]˂s[i]$senumeration$pre$transfer#include 使用namespacestd;类型deflonglongll;组成MAXN=2e3+10,MOD=1e9+7;intn,k;字符[MAXN];llpre[MAXN][MAXN]、dp[MAXN][MAXN];intmain(){scanf;dp[0][0]=pre[0][0]=1;for{dp[i][j]=pre[i-1][j]*%MOD;for%=MOD;pre[i][j]=%MOD,}printf;return0;}问题C

Link:

Codeforces #210 传送门

A:

贪心,对每个值都取最大值,不会有其他解使答案变优

[Codeforces #210] Tutorial第1张[Codeforces #210] Tutorial第2张
#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> P;
typedef double db;
const int MAXN=5005,INF=1<<30;
struct data{int op,l,r,x;}dat[MAXN];
int n,m,mx[MAXN],vis[MAXN];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d%d",&dat[i].op,&dat[i].l,&dat[i].r,&dat[i].x);
    for(int i=1;i<=n;i++)
    {
        int tmp=0;mx[i]=INF;
        for(int j=1;j<=m;j++)
            if(dat[j].op==1&&i>=dat[j].l&&i<=dat[j].r) 
                tmp+=dat[j].x;
            else if(dat[j].op==2&&i>=dat[j].l&&i<=dat[j].r)
                mx[i]=min(mx[i],dat[j].x-tmp);
    }
    for(int i=1;i<=n;i++)
    {
        if(mx[i]==INF) mx[i]=0;
        int tmp=mx[i];
        for(int j=1;j<=m;j++)
            if(dat[j].op==1&&i>=dat[j].l&&i<=dat[j].r) 
                tmp+=dat[j].x;
            else if(dat[j].op==2&&i>=dat[j].l&&i<=dat[j].r&&tmp==dat[j].x)
                vis[j]++;
    }
    for(int i=1;i<=m;i++)
        if(dat[i].op==2&&!vis[i]) return puts("NO"),0;
    puts("YES");
    for(int i=1;i<=n;i++) 
        printf("%d ",mx[i]);
    return 0;
}
Problem A

B:

答案可行性单调,二分答案

每次判断用$dp[i]$表示到$i$只要要删多少个数,$i$必取

[Codeforces #210] Tutorial第3张[Codeforces #210] Tutorial第4张
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=2e3+10;
int n,k,l,r,dat[MAXN],dp[MAXN];

bool check(int x)
{
    int ret=n;
    for(int i=1;i<=n;i++) dp[i]=i-1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
            if(abs(dat[i]-dat[j])<=1ll*x*(i-j))
                dp[i]=min(dp[i],dp[j]+i-j-1);
    for(int i=1;i<=n;i++)
        ret=min(ret,dp[i]+n-i);
    return ret<=k;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&dat[i]);
    l=0;r=2e9;
    while(l<=r)
    {//注意爆long long
        int mid=l/2+r/2+(l%2+r%2)/2;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}
Problem B

$i$必取这个条件一定要加,否则无法转移

同时注意二分时$l+r$可能爆$longlong$

C:

想到从前往后$dp$,每次按以$i$为左端点时对答案的贡献转移

但这样在$t[i]=s[i]$时是后项相关的,不符合$dp$要求

因此要将$t[i]=s[i]$合并在$t[i]>s[i]$中计算,$t[i]>s[i]$时的贡献变为$(pre+1)*(n-i+1)$

$dp[i][j]$:以前$i$位为左端点结果为$j$的方案数,分$t[i]>s[i]$与$t[i]<s[i]$枚举$pre$转移

[Codeforces #210] Tutorial第5张[Codeforces #210] Tutorial第6张
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN=2e3+10,MOD=1e9+7;
int n,k;char s[MAXN];
ll pre[MAXN][MAXN],dp[MAXN][MAXN];

int main()
{
    scanf("%d%d%s",&n,&k,s+1);
    dp[0][0]=pre[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
        {
            dp[i][j]=pre[i-1][j]*(s[i]-'a')%MOD;
            for(int k=0;(k+1)*(n-i+1)<=j&&k<i;k++)
                (dp[i][j]+=dp[i-k-1][j-(k+1)*(n-i+1)]*('z'-s[i]))%=MOD;
            pre[i][j]=(pre[i-1][j]+dp[i][j])%MOD;
        }
    printf("%lld",pre[n][k]);
    return 0;
}
Problem C

免责声明:文章转载自《[Codeforces #210] Tutorial》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[Codeforces #188] Tutorial[ARC 066] Tutorial下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

弹出窗口与选择器(五)

9.5 JFileChooser类 Swing组件集合同时提供了用于选择文件名字与目录的选择器:JFileChooser类。这个选择器替换了原始AWT组件集合中使用FileDialog的需要。类似于其他的Swing选择器组件,JFileChooser并没有自动被放入一个弹出窗口中,但是他可以放在我们程序中用户界面的任何地方。图9-25显示了一个具有Metal...

UVA 10943全加和(规律)

f(n,k)=f(0,k-1)+f(1,k-1)+.......f(n,k-1) #include <iostream> #include <cstring> using namespace std; int main() { int n,k,i,j,a[105][105],l; while(cin>>n>>...

NuSOAP webservice接口使用详解

PHP SOAP服务器 用PHP和NuSoap来建立SOAP服务器非常容易。基本上,你只要写出你想要暴露给你的Web services的函数,然后用NuSoap去注册它们就可以了。OK,另外还需要两步才能完成PHP SOAP服务器的建立。首先你还要在你的PHP代码中创建NuSoap对象的一个实例,然后用HTTP POST方法将原始数据传给NuSoap进行处理...

NetBeans 时事通讯(刊号 # 61 Jun 25, 2009)

刊号 # 61 - Jun 25, 2009 项目新闻 GlassFish ESB v2.1 已发布——包括 NetBeans 6.5 开源项目 OpenESB 已经发布了最新版本:GlassFish ESB v2.1。此次发布包括了作为设计工具的 NetBeans IDE 6.5.1 和作为运行时的 GlassFish。下载包含...

Android TabWidget

首先先看一个小例子,接着讲解原理 TabTest.java viewplaincopytoclipboardprint? packageorg.hualang.tab; importandroid.app.Activity; importandroid.app.TabActivity; importandroid.graphi...

不允许一个用户使用一个以上用户名域一个服务器或共享

平时使用共享文件夹的时候遇到的问题,提示: “***无法访问。您可能没有权限使用网络资源。请与这台服务器的管理员联系以查明您是否有访问权限。不允许一个用户使用一个以上用户名与一个服务器或共享资源的多重连接。中断与此服务器或共享资源的所有连接,然后再试一次...” 在某论坛找到了解决办法,觉得同学回答的到位,特此记录。 问: 加域时出现错误:不允许一个用户使...