头像

Overnoise

ZTOI


访客:14367

离线:5小时前



Overnoise
17小时前

【题目描述】

XY在玩一个包含N个任务的游戏。每个任务完成时限为Ti(你可以认为还没开始做任务时的时间为0),奖励为Wi。由于XY技术的娴熟以及任务的简单,对于每个任务,他都可以在一个单位时间内完成。

XY想要知道他能够获得的最多的奖励。

【输入】

第一行一个整数N,表示需要完成的任务数目。

接下来N行,每行两个整数T、W,分别表示完成这个任务的最后期限和完成这个任务后获得的奖励。

【输出】

输出数据有且仅有一行,只包含一个整数,表示最多获得的奖励。

【输入样例】

2
1 5
1 4

【输出样例】

5

【样例输入2】

5
2 3
1 2
4 5
1 3
3 4

【样例输出2】

15

【样例解释2】

对于样例2,XY可以选择完成任务1、3、4 和5,这样他可以获得奖励15。

【数据规模及约定】

对于10%的数据,N≤100,Ti≤100,Wi≤2000。

对于30%的数据,N≤1000,Ti≤5000,Wi≤2000。

对于50%的数据,N≤10000,Ti≤20000,Wi≤2000。

对于100%的数据,N≤200000,Ti≤200000,Wi≤2000。

思路

首先考虑贪心
1.我们首先需要完成获利大的任务(所以排序)
2.完成任务时尽量安排晚一点完成(为其他任务留时间,所以从最晚时间点向前找)

所以贪心裸代码如下

#include<bits/stdc++.h>
using namespace std;
struct oppo{
    int s,w;
}e[1000006];
bool rule(oppo a,oppo b)
{
    return a.w>b.w;
}
int n,ans;
bool f[200005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>e[i].s>>e[i].w;
    sort(e+1,e+n+1,rule);
    for(int i=1;i<=n;i++)
    {
        for(int j=e[i].s;j>=1;j--)
            if(!f[j])
            {
                ans+=e[i].w;
                f[j]=1;
                break;
            }
    }
    cout<<ans<<endl;
    return 0;
}

交上去,完美超时
什么原因呢?
你看这个东西

    for(int i=1;i<=n;i++)
    {
        for(int j=e[i].s;j>=1;j--)
            if(!f[j])
            {
                ans+=e[i].w;
                f[j]=1;
                break;
            }
    }

这复杂度T飞了好吧
所以我们考虑路径压缩
AC代码如下

#include<bits/stdc++.h>
using namespace std;
struct oppo{
    int s,w;
}e[1000006];
bool rule(oppo a,oppo b)
{
    return a.w>b.w;
}
int n,ans;
int f[200005];
int main()
{
    cin>>n;
    for(int i=0;i<=200000;i++)
        f[i]=i-1;
    for(int i=1;i<=n;i++)
        cin>>e[i].s>>e[i].w;
    sort(e+1,e+n+1,rule);
    for(int i=1;i<=n;i++)
        if(f[e[i].s]!=-1){
            f[e[i].s]=f[f[e[i].s]];
            ans+=e[i].w;
        }
    cout<<ans<<endl;
    return 0;
}



Overnoise
17小时前

题目链接

扑克牌

时间限制: 1000 ms 内存限制: 262144 KB

【题目描述】
一副扑克牌有n张牌。一般你买的一副新扑克牌里除了这n张牌外还会有一些张特殊的牌,如果你不小心弄丢了n张牌中的某一张,就可以用特殊牌来代替,但是如果你弄丢两张的话就没有办法了,因为特殊牌上的图案是一样的。

现在你得到了很多扑克牌,准确来说,n种牌你各有a1,a2,…,an张,同时你还有b张特殊牌,现在你需要从这些牌中整理出若干副牌供大家使用。整理出的一副牌可以由n种普通牌各一张组成,也可以由n−1种普通牌各一张再加一张特殊牌组成。

请你设计出一种方案,整理出尽可能多的牌。

【输入】
第一行给出n和b。

第二行给出a1,a2,…,an。

【输出】
输出最多能整理出的牌的副数。

【输入样例】
5 5
5 5 5 5 5
【输出样例】
6
【提示】

【数据规模及约定】

对于20%的数据,1≤n≤100,牌的数量小于100。

对于40%的数据,1≤n≤3000。

对于100%的数据,1≤n≤1000000,牌的数量≤10^6。

思路

每副牌最多一张特殊卡
使用能用特殊卡就用特殊卡,把普通卡留给后面用

参考程序

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 1000006
using namespace std;
int n,m=N,b,ans,c;
int a[N];
int main() {
    cin>>n>>b;
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        m=min(m,a[i]);
    }
    c=min(m,b);
    ans+=m;
    while(c) {
        b-=c;
        for(int i=1; i<=n; i++)
            a[i]-=m;
        for(int i=0; c; i++)
            for(int j=1; j<=n&&c; j++)
                if(a[j]==i) {
                    c--;
                    a[j]++;
                }
        m=N;
        for(int i=1; i<=n; i++)
            m=min(m,a[i]);
        ans+=m;
        c=min(m,b);
    }
    while(b) {
        int k=0;
        for(int i=1; i<=n&&k<2; i++) {
            if(a[i]==0)
                k++;
            else
                a[i]--;
        }
        if(k==2)
            break;
        b--;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}




题目链接
题目.png
预处理标记每个点j秒后的影响
进行迭代加深记忆化搜索即可

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 20
#define M 1000
using namespace std;

int n;
int fa[N];
int a,s,k,v;
int f[N][N];
int flag[1<<17];
void dfs(int x) {
    if(v==a) {//满足条件退出
        cout<<k<<endl;
        exit(0);
    }
    if(x==k) return;
    for(int i=1; i<=n; i++) {//枚举选点
        v^=f[i][k-x];
        if(x<flag[v]) {//记忆化搜索
            flag[v]=x;
            dfs(x+1);
        }
        v^=f[i][k-x];
    }
    dfs(x+1);//不标记点
}
int main() {
    cin>>n;
    for(int i=2; i<=n; i++)
        cin>>fa[i];//输入爸爸
    for(int i=1; i<=n; i++) {
        cin>>s;
        a=a*2+s;//输入最终状态,转为2进制
    }
        //求标记第i个点j秒后会影响的点(2进制)
    for(int i=1; i<=n; i++) {
        int x=i;
        for(int j=1; j<=n; j++) {
            if(x)//特判 x为0不会影响点
                f[i][j]=f[i][j-1]|(1<<(n-x));
            else
                f[i][j]=f[i][j-1];
            x=fa[x];//向上移
        }
    }
    for(k=0; k<=n; k++) {//迭代加深
                memset(flag,10,sizeof(flag));
        dfs(0);
    }
    puts("frog");
    return 0;
}



分析.png
分析来自

#include<bits/stdc++.h>
#define N 2005
using namespace std;
int n,m,v,e;
int c[N],d[N];
double k[N];
int s,t,w;
int rood[305][305];
double dp[N][N][3],ans=999999999;
int main()
{
    memset(rood,10,sizeof(rood));
    for(int i=0;i<=300;i++) rood[i][i]=0;
    for(int i=0;i<=2000;i++) for(int j=0;j<=4000;j++) dp[i][j][0]=dp[i][j][1]=ans;
    cin>>n>>m>>v>>e;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<=n;i++) cin>>k[i];
    for(int i=1;i<=e;i++){
        cin>>s>>t>>w;
        rood[s][t]=min(rood[s][t],w);
        rood[t][s]=min(rood[t][s],w);
    }
    for(int z=1;z<=v;z++)
        for(int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                rood[i][j]=min(rood[i][j],rood[i][z]+rood[z][j]);
    dp[1][m][0]=0;
    if(m) dp[1][m-1][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j][0]=min(dp[i][j][0], dp[i-1][j][0]   + rood[c[i-1]][c[i]] );
            dp[i][j][0]=min(dp[i][j][0], dp[i-1][j][1]   + k[i-1]*rood[d[i-1]][c[i]]      + (1.0-k[i-1])*rood[c[i-1]][c[i]] );
            dp[i][j][1]=min(dp[i][j][1], dp[i-1][j+1][0] + k[i]*rood[c[i-1]][d[i]]        + (1.0-k[i])*rood[c[i-1]][c[i]]   );
            dp[i][j][1]=min(dp[i][j][1], dp[i-1][j+1][1] + k[i-1]*k[i]*rood[d[i-1]][d[i]] + (1.0-k[i-1])*k[i]*rood[c[i-1]][d[i]] + k[i-1]*(1.0-k[i])*rood[d[i-1]][c[i]] +(1.0-k[i-1])*(1.0-k[i])*rood[c[i-1]][c[i]] );
        }
    }
    for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2f\n",ans);
    return 0;
}



淀粉质真好吃(点分治)

#include<bits/stdc++.h>
#define N 200005
#define M 1000006
#define inf 10000007
using namespace std;
struct oppo{
    int to,w,next;
}rood[N*2];
int head[N],tot;
void add(int from,int to,int w)
{
    rood[++tot].to=to;
    rood[tot].next=head[from];
    rood[tot].w=w;
    head[from]=tot;
}
int n,k,sum,ans=999999;
int s,t,d;
bool vis[N];
int rt;
int maxp[N];
int siz[N];
void getrt(int x,int fa)
{
    maxp[x]=0,siz[x]=1;
    for(int i=head[x];i;i=rood[i].next){
        int to=rood[i].to;
        if(to==fa||vis[to]) 
            continue;
        getrt(to,x);
        maxp[x]=max(maxp[x],siz[to]);
        siz[x]+=siz[to];
    }
    maxp[x]=max(sum-siz[x],maxp[x]);
    if(maxp[x]<maxp[rt])
        rt=x;
}
int rem[N];
int dis[N];
bool flag[M];
int dep[N];
int bs[N];
int minbs[M];
void getdis(int x,int fa)
{
    if(dis[x]>k)
        return;
    rem[++rem[0]]=dis[x];
    bs[++bs[0]]=dep[x];
    for(int i=head[x];i;i=rood[i].next)
    {
        int to=rood[i].to;
        if(vis[to]||to==fa)
            continue;
        dis[to]=dis[x]+rood[i].w;
        dep[to]=dep[x]+1;
        getdis(to,x);
    }
}
queue< int > v;
void laca(int x)
{
    flag[0]=1;
    minbs[0]=0;
    for(int i=head[x];i;i=rood[i].next)
    {
        int to=rood[i].to;
        if(vis[to])
            continue;
        rem[0]=bs[0]=0;
        dis[to]=rood[i].w;
        dep[to]=1;
        getdis(to,-1);
        for(int j=1;j<=rem[0];j++)
        {
            //cout<<rem[j]<<"--"<<bs[j]<<endl;
            if(k>=rem[j]&&flag[k-rem[j]])
                ans=min(ans,bs[j]+minbs[k-rem[j]]);
        }
        for(int j=1;j<=rem[0];j++){
            v.push(rem[j]);
            flag[rem[j]]=1;
            minbs[rem[j]]=min(minbs[rem[j]],bs[j]);
        }
    }
    while(v.size()){
        int fr=v.front();
        flag[fr]=0;
        minbs[fr]=inf;
        v.pop();
    }
}
void work(int x)
{
    vis[x]=1;
    laca(x);
    for(int i=head[x];i;i=rood[i].next)
    {
        int to=rood[i].to;
        if(vis[to])
            continue;
        maxp[rt=0]=inf;
        sum=siz[to];
        getrt(to,-1);
        getrt(to,-1);
        work(rt);
    }
}
int main()
{
    memset(minbs,10,sizeof(minbs));
    cin>>n>>k;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&s,&t,&d);
        add(s,t,d);
        add(t,s,d);
    }
    maxp[rt=0]=inf;
    sum=n;
    getrt(rt,-1);
    getrt(rt,-1);
    work(rt);
    if(ans==999999) ans=-1;
    cout<<ans<<endl;
    return 0;
}




T1

题目链接
tm.png

分析

对于 n,m<=1000 的点直接使用DP即可 可得20分
对于 n,m<=100000 的点我们可以发现k很小
考虑使用容斥原理
我们定义一个work函数
work是指右移a次上移b次有多少种移法

work解决方法:

1.考虑把b次上移插入a次右移动的空中 a有a+1个空 所以a + +
2.问题转变为类似放苹果的问题 即:有b个苹果,放入a个不同的盘子有多少种放法(盘子可以为空)
3.既然盘子可以为空,但是考虑插空做法盘子不能为空 苹果数+=盘子数 即 b+=a
4.考虑插空,有a个盘子,所以有a+1个插板,但是最两边的空一定有插板, a + + ,a-=2; 即a - -
5.b个苹果有b+1个空,但是最两边的空一定有插板, b + + ,b - =2; 即b - -
6.调用组合数得出答案

work代码如下

LL work(LL a,LL b) {
    a++;
    b+=a;
    b--;
    a--;
    return C(a,b);
}

如果求逆元用线性求逆元会更快一些

关于容斥

1.ans+没有障碍的情况
2.如果有障碍,枚举每个障碍 求出经过这个障碍的路径有多少条,减去(如何求见代码,思维难度不大)
3.如果k>=2 , 枚举每2个障碍 求出经过这2个障碍的路径有多少条,加(如何求见代码,思维难度不大)
3.如果k==2 , 求出经过这3个障碍的路路径有多少条,减去(如何求见代码,思维难度不大)

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m,k,s,t;
bool f[1005][1005];
LL dp[1005][1005];
LL x[10],y[10];
LL mod=998244353;
LL ksm(LL a) {
    LL b=mod-2;
    LL ans=1;
    while(b) {
        if(b&1)
            ans=(a*ans)%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
LL ni[100005];
void csh() {
    for(LL i=1; i<=100000; i++)
        ni[i]=ksm(i);
}
LL C(LL a,LL b) {
    LL a1=1;
    for(LL i=b; i>=b-a+1; i--)
        a1=a1*i%mod;
    for(LL i=1; i<=a; i++)
        a1=(a1*ni[i])%mod;
    return a1;
}
LL work(LL a,LL b) {
    a++;
    b+=a;
    b--;
    a--;
    return C(a,b);
}
int main() {
    cin>>n>>m>>k;
    m++;n++;
    if(n<=1000&&m<=1000) {
        for(LL i=1; i<=k; i++) {
            cin>>s>>t;
            f[s][t]=1;
        }
        dp[n][1]=1;
        for(LL i=n; i>0; i--)
            for(LL j=1; j<=m; j++)
                if((i!=n||j!=1)&&f[i][j]!=1)
                    dp[i][j]=(dp[i+1][j]+dp[i][j-1])%mod;
        cout<<dp[1][m]<<"\n";
    }
    else {
        csh();
        LL ans=work(n-1,m-1);
        for(LL i=1; i<=k; i++) {
            cin>>x[i]>>y[i];
            x[i]=n-x[i];
            y[i]--;
            ans=(ans-work(x[i],y[i])*work(n-x[i]-1,m-y[i]-1))%mod;
        }
        for(LL i=1; i<=k; i++)
            for(LL j=i+1; j<=k; j++)
                if(x[i]+y[i]>x[j]+y[j]) {
                    swap(x[i],x[j]);
                    swap(y[i],y[j]);
                }
        if(k>=2)
            for(LL i=1; i<=k; i++)
                for(LL j=i+1; j<=k; j++)
                    if(x[j]>=x[i]&&y[j]>=y[i])
                        ans=(ans+work(x[i],y[i])*work(x[j]-x[i],y[j]-y[i])%mod*work(n-x[j]-1,m-y[j]-1))%mod;
        if(k==3)
            if(x[3]>x[2]&&x[2]>x[1])
                if(y[3]>y[2]&&y[2]>y[1])
                    ans-=work(x[1],y[1])*work(x[2]-x[1],y[2]-y[1])%mod*work(x[3]-x[2],y[3]-y[2])%mod*work(n-x[3]-1,m-y[3]-1)%mod;
        cout<<(ans+mod)%mod<<endl;
    }
    return 0;
}



这明显是个淀粉质(点分治)啊

点分治入门
思路:

如果求等于K的路径条数,非常简单。

本题求小于等于K的路径条数,可以考虑改变统计答案的方法。

原本统计答案是对于一个路径长度len,判断K-len在之前的子树中出现多少次。

现在统计答案是对于一个路径长度len,判断小于等于K-len的数在之前的子树中出现多少次。

之前我们用一个桶数组f来辅助,f[i]表示i这个值是否出现过。

现在我们用树状数组维护桶数组,即可用一个log的复杂度来平衡单点修改和求前缀和的复杂度。

点分治O(logn),枚举子树O(n),统计答案O(logn),由于使用树状数组,常数较小。

但是我第一次直接用memset清零树状数组,直接T飞了

所以改为记录后反向剪(居然没T,有点玄学)

参考代码

#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 40004
using namespace std;
struct oppo {
    int to,w,next;
} rood[N*2];
int head[N],tot;
void add(int from,int to,int Long) {
    rood[++tot].to=to;
    rood[tot].w=Long;
    rood[tot].next=head[from];
    head[from]=tot;
}
int n,m,s,t,w,ask,ans,rt,sum;
int maxp[N],siz[N],rem[N],dis[N],v[5000005];
bool vis[N];
void getrt(int x,int fa) { //找重心
    siz[x]=1;
    maxp[x]=0;
    for(int i=head[x]; i; i=rood[i].next) {
        if(rood[i].to==fa||vis[rood[i].to])
            continue;
        getrt(rood[i].to,x);
        siz[x]+=siz[rood[i].to];
        maxp[x]=max(maxp[x],siz[rood[i].to]);
    }
    maxp[x]=max(maxp[x],sum-siz[x]);
    if(maxp[x]<maxp[rt]) rt=x;
}
void getdis(int x,int fa) {
    rem[++rem[0]]=dis[x];
    for(int i=head[x]; i; i=rood[i].next) {
        if(rood[i].to==fa||vis[rood[i].to])
            continue;
        dis[rood[i].to]=dis[x]+rood[i].w;
        if(dis[rood[i].to]<=ask)
            getdis(rood[i].to,x);
    }
}
void vadd(int x,int ad) {
    x++;
    for(; x<=ask+10; x+= x&(-x) ) v[x]+=ad;
}
int vask(int x) {
    x++;
    int all=0;
    for(x; x>0; x-= x&(-x) ) all+=v[x];
    return all;
}
queue<int> k;
void calc(int x) {
    vadd(0,1);
    for(int i=head[x]; i; i=rood[i].next) {
        int to=rood[i].to;
        if(vis[to]) continue;
        rem[0]=0;
        dis[to]=rood[i].w;
        getdis(to,x);
        for(int j=1; j<=rem[0]; j++)
            if(ask>=rem[j])
                ans+=vask(ask-rem[j]);
        for(int j=rem[0]; j; --j) {
            vadd(rem[j],1);
            k.push(rem[j]);
        }

    }
    while(k.size()) {
        vadd(k.front(),-1);
        k.pop();
    }
    vadd(0,-1);
}
void work(int x) {
    vis[x]=1;
    calc(x);
    for(int i=head[x]; i; i=rood[i].next) {
        if(vis[rood[i].to])
            continue;
        sum=siz[rood[i].to];
        maxp[rt=0]=N;
        getrt(rood[i].to,-1);
        getrt(rt,-1);
        work(rt);
    }
}
int main() {
    while(1) {
        ans=0;
        tot=0;
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        cin>>n>>ask;
        if(n==0)
            return 0;
        for(int i=1; i<n; i++) {
            scanf("%d%d%d",&s,&t,&w);
            add(s,t,w);
            add(t,s,w);
        }
        maxp[rt=0]=sum=n;
        getrt(1,-1);
        getrt(rt,-1);
        work(rt);
        cout<<ans<<endl;
    }
}



分类讨论即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,i1,i2,s[9],ans=0,o,m;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        i1=i%100;
        i2=i%10000/100;
        if(i2>12||i2==0)
        continue;
        if(i2==1||i2==3||i2==5||i2==7||i2==8||i2==10||i2==12) o=31;
        else if(i2==2) o=29;
        else o=30;
        if(i1>o||i1==0) continue;
        m=i;
        for(int l=0;m>0;l++){
            s[l]=m%10;
            m=m/10;
        }
        if(i2<=12&&i1<=o&&s[0]==s[7]&&s[1]==s[6]&&s[2]==s[5]&&s[3]==s[4])
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}



枚举时间,模拟即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("water.in","r",stdin);
    //freopen("water.out","w",stdout);
    int n,m,a[10010],t,c=1,f=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];  
    } 
    for(t=0;;t++){
        for(int o=1;o<=m;o++){
            a[o]=a[o]-1;
            if(a[o]==0&&m+c<=n){
                a[o]=a[m+c];
                c++;
            }
        }
        if(m+c>n)   {
                for(int l=1;l<=m;l++){
                    if(a[l]>0){
                        f=0;
                        break;
                    }
                    else
                    f=1;
                }
            }
        if(f==1)
            break;
    }
    cout<<t+1<<endl;
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
struct mmp
{
    int china;
    int math;
    int eng;
    int all;
    int xh;
};
int main()
{
    //freopen("scholar.in","r",stdin);
    //freopen("scholar.out","w",stdout);
    mmp a[400];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].china>>a[i].math>>a[i].eng;
        a[i].xh=i;
        a[i].all=a[i].china+a[i].math+a[i].eng;
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(a[j].all>a[i].all)
                swap(a[j],a[i]);
            if(a[i].all==a[j].all)
            {
                if(a[j].china>a[i].china)
                    swap(a[i],a[j]);
                if(a[j].china==a[i].china)
                    if(a[j].xh<a[i].xh)
                        swap(a[i],a[j]);
            }
        }
    for(int i=1;i<=5;i++)
        cout<<a[i].xh<<" "<<a[i].all<<endl;
    return 0;
}