noip济南清北冲刺班DAY1

上午

T1 立方数

题目描述

LYK定义了一个数叫“立方数”，若一个数可以被写作是一个正整数的3次方，则这个数就是立方数，例如1,8,27就是最小的3个立方数。

现在给定一个数P，LYK想要知道这个数是不是立方数。

当然你有可能随机输出一些莫名其妙的东西来骗分，因此LYK有T次询问~

输入输出格式

输入格式：

第一行一个数T，表示有T组数据。

接下来T行，每行一个数P。

输出格式：

输出T行，对于每个数如果是立方数，输出“YES”，否则输出“NO”。

输入输出样例

输入样例#1：

输出样例#1：

YES
YES
NO

说明

对于30%的数据p<=100。

对于60%的数据p<=10^6。

对于100%的数据p<=10^18，T<=100。

题解：枚举10^6/二分。

代码：二分0ms,枚举540ms

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

int t;
LL x;

LL read(){
    LL x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    
}

bool check(LL x){
    for(int i=1;;i++){
        if(1LL*i*i*i==x)return true;
        if(1LL*i*i*i>x)return false;
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&x);
        if(check(x))printf("YES
");
        else printf("NO
");
    }
    return 0;
}

枚举

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        long long x;
        scanf("%lld",&x);
        long long l=1,r=1000000;
        bool flag=false;
        while(l<=r){
            int mid=(l+r)>>1;
            long long gg=1LL*mid*mid*mid;
            if(gg==x){
                flag=true;break;//不break死循环 
            }
            else if(gg>x)r=mid-1;
            else l=mid+1;
        }
        if(flag)printf("YES
");
        else printf("NO
");
    }
    return 0;
}

二分

T2立方数2

题目描述

LYK定义了一个数叫“立方数”，若一个数可以被写作是一个正整数的3次方，则这个数就是立方数，例如1,8,27就是最小的3个立方数。

LYK还定义了一个数叫“立方差数”，若一个数可以被写作是两个立方数的差，则这个数就是“立方差数”，例如7(8-1),26(27-1),19(27-8)都是立方差数。

现在给定一个数P，LYK想要知道这个数是不是立方差数。

当然你有可能随机输出一些莫名其妙的东西，因此LYK有T次询问~

这个问题可能太难了…… 因此LYK规定P是个质数！

输入输出格式

输入格式：

第一行一个数T，表示有T组数据。

接下来T行，每行一个数P。

输出格式：

输出T行，对于每个数如果是立方差数，输出“YES”，否则输出“NO”。

输入输出样例

输入样例#1：复制

输出样例#1：复制

NO
NO
NO
YES
NO

说明

对于30%的数据p<=100。

对于60%的数据p<=10^6。

对于100%的数据p<=10^12，T<=100。

题解：立方差公式

设p=x^3-y^3

=(x-y)*(x^2+xy+y^2)

因为p是个素数，所以x-y=1,x^2+xy+y^2=p。

所以x=y+1,代入x^2+xy+y^2得，

(y+1)^2+(y+1)*y+y^2=p

3*y^2+3y+1=p

所以10^3枚举y就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

int t;

bool check(LL x){
    for(int i=1;;i++){
        LL tmp=3LL*i*i+3*i+1;
        if(tmp==x)return true;
        if(tmp>x)return false;
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        LL p;
        scanf("%lld",&p);
        if(check(p))printf("YES
");
        else printf("NO
");
    }
    return 0;
}

T3 猜数字

题目描述

LYK在玩猜数字游戏。

总共有n个互不相同的正整数，LYK每次猜一段区间的最小值。形如[li,ri]这段区间的数字的最小值一定等于xi。

我们总能构造出一种方案使得LYK满意。直到…… LYK自己猜的就是矛盾的！

例如LYK猜[1,3]的最小值是2，[1,4]的最小值是3，这显然就是矛盾的。

你需要告诉LYK，它第几次猜数字开始就已经矛盾了。

输入输出格式

输入格式：

第一行两个数n和T，表示有n个数字，LYK猜了T次。

接下来T行，每行三个数分别表示li,ri和xi。

输出格式：

输出一个数表示第几次开始出现矛盾，如果一直没出现矛盾输出T+1。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

对于50%的数据n<=8，T<=10。

对于80%的数据n<=1000，T<=1000。

对于100%的数据1<=n,T<=1000000,1<=li<=ri<=n,1<=xi<=n（但并不保证一开始的所有数都是1~n的）。

题解：

线段树骗分20

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10000
#define inf 10000000
using namespace std;

int n,t;
struct Tree{
    int l,r,mn,mx,s;
}tr[maxn<<2];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}

void pushup(int rt){
    tr[rt].mn=min(tr[rt<<1].mn,tr[rt<<1|1].mn);
    tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
    return ;
}

void pushdown(int rt){
    if(tr[rt].s==0)return;
    tr[rt<<1].mn=tr[rt<<1].mx=tr[rt].s;
    tr[rt<<1|1].mn=tr[rt<<1|1].mx=tr[rt].s;
    tr[rt].s=0;
}

void build(int rt,int l,int r){
    tr[rt].l=l;tr[rt].r=r;
    if(l==r){
        tr[rt].mn=tr[rt].mx=inf;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    pushup(rt);
}

void modify(int rt,int l,int r,int ql,int qr,int c){
    if(l>=ql&&r<=qr){
        tr[rt].mn=tr[rt].mx=c;
        tr[rt].s=c;
        return;
    }
    int mid=(l+r)>>1;
    if(ql<=mid)modify(rt<<1,l,mid,ql,qr,c);
    if(qr>mid)modify(rt<<1|1,mid+1,r,ql,qr,c);
    pushup(rt);
}

int query_mn(int rt,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr){
        return tr[rt].mn;
    }
    pushdown(rt);
    int mid=(l+r)>>1,ans=inf;
    if(ql<=mid)ans=min(ans,query_mn(rt<<1,l,mid,ql,qr));
    if(qr>mid)ans=min(ans,query_mn(rt<<1|1,mid+1,r,ql,qr));
    return ans;
}

int query_mx(int rt,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr){
        return tr[rt].mx;
    }
    pushdown(rt);
    int mid=(l+r)>>1,ans=-inf;
    if(ql<=mid)ans=max(ans,query_mx(rt<<1,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,query_mx(rt<<1|1,mid+1,r,ql,qr));
    return ans;
}

int main(){
    n=read();t=read();
    if(n>maxn){
        printf("%d
",t+1);
        fclose(stdin);fclose(stdout);
        return 0;
    }
    build(1,1,n);
    int l,r,x;
    for(int i=1;i<=t;i++){
        int l,r,x;
        l=read();r=read();x=read();
        int mn=query_mn(1,1,n,l,r);
        int mx=query_mx(1,1,n,l,r);
        if(x>mn||(x<mn&&mx!=inf)){
            printf("%d
",i);
            fclose(stdin);fclose(stdout);
            return 0;
        }
        modify(1,1,n,l,r,x);
    }
    printf("%d
",t+1);
    return 0;
}

判定性问题

题目大意：给定一堆询问，问出现矛盾的询问是哪一条。

方法:

1)枚举+判断

2)二分

l=1,r=q

如果在询问在mid时候已经出现了矛盾，出现矛盾的地方一定在mid左边。

那么现在的问题已经缩小在了mid左边。

具体做法是将1--mid的询问按照min值从大到小排序。依次覆盖区间，

那么不合法的情况有两个：

a、两个区间min值相同，但是不相交。因为数都是不同的。

b、枚举的当前区间已经被之前的区间覆盖了。

那么只需要维护一下这个区间是否被覆盖了。

线段树是会T的。用并查集维护。fa[i]表示从i开始右边第一个没有被区间覆盖的点。

在处理注意：对于最小值相同的，我们要求区间交和区间并，那么最小值一定在

区间并里。只要判断当前区间有没有之前区间覆盖。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000009
using namespace std;

int n,m,l,r,mid,ans,lmn,lmx,rmn,rmx;
int fa[maxn];

inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct Q{
    int l,r,mn;
}q[maxn],t[maxn];

bool cmp(Q a,Q b){
    return a.mn>b.mn;
}

int f(int x){
    return fa[x]==x?x:fa[x]=f(fa[x]);
}

bool check(int k){
    for(int i=1;i<=n+1;i++)fa[i]=i;
    for(int i=1;i<=k;i++)t[i]=q[i];
    sort(t+1,t+k+1,cmp);
    lmn=lmx=t[1].l;rmn=rmx=t[1].r;
    for(int i=2;i<=k;i++){
        if(t[i].mn<t[i-1].mn){
            if(f(lmx)>rmn)return true;
            for(int j=f(lmn);j<=rmx;j=f(j+1))
             fa[f(j)]=f(rmx+1);
            lmn=lmx=t[i].l;rmn=rmx=t[i].r;
        }else{
            lmn=min(lmn,t[i].l);lmx=max(lmx,t[i].l);
            rmn=min(rmn,t[i].r);rmx=max(rmx,t[i].r);
            if(lmx>rmn)return true;
        }
    }
    if(f(lmx)>rmn)return true;
    return false;
}

int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].mn=read();
    l=1;r=m;ans=m+1;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d
",ans);
    return 0;
}

下午

T1 水题

题目描述

LYK出了道水题。

这个水题是这样的：有两副牌，每副牌都有n张。

对于第一副牌的每张牌长和宽分别是xi和yi。对于第二副牌的每张牌长和宽

分别是aj和bj。第一副牌的第i张牌能覆盖第二副牌的第j张牌当且仅当xi>=aj

并且yi>=bj。（注意牌不能翻转）当然一张牌只能去覆盖最多一张牌，而不

能覆盖好多张。LYK想让两副牌的各n张一一对应叠起来。它想知道第二副

牌最多有几张能被第一副牌所覆盖。

输入输出格式

输入格式：

第一行一个数n。

接下来n行，每行两个数xi,yi。

接下来n行，每行两个数aj,bj。

输出格式：

输出一个数表示答案。

输入输出样例

输入样例#1：复制

输出样例#1：复制




题解：

错误贪心

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10009
using namespace std;

int n,ans,vis[maxn];

struct ZFX{
    int x,y;
}a[maxn],b[maxn];

bool cmp(ZFX a,ZFX b){
    return a.x<b.x;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++)scanf("%d%d",&b[i].x,&b[i].y);
    sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[j])continue;
            if(a[i].x>=b[j].x&&a[i].y>=b[j].y){
                vis[j]=true;ans++;break;
            }
        }
    }
    printf("%d
",ans);
    return 0;
}

正解：对于ai,我们把长度小于ai的b类牌放入一个集合，找到

高度最小的进行覆盖。用个数据结构维护一下....

stl set知道吧....set是没有重复元素，multiset是有重复元素。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#define maxn 100009
using namespace std;
multiset<int>q;
int n,k,ans;

struct T{
    int x,y;
}a[maxn],b[maxn];

bool cmp(T a,T b){
    return a.x<b.x;
}

int main(){
    scanf("%d",&n);k=1;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++)scanf("%d%d",&b[i].x,&b[i].y);
    sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
    q.clear();
    for(int i=1;i<=n;i++){
        while(b[k].x<=a[i].x&&k<=n){
            q.insert(b[k].y);k++;
        }
        if(q.empty())continue;
        multiset<int>::iterator it=q.upper_bound(a[i].y);
        if(it==q.begin())continue;
        ans++;it--;q.erase(it);
    }
    cout<<ans<<endl;
}

T2 梦境

题目描述

LYK做了一个梦。

这个梦是这样的，LYK是一个财主，有一个仆人在为LYK打工。

不幸的是，又到了月末，到了给仆人发工资的时间。但这个仆人很奇怪，它可能想要至少x块钱，并且当LYK凑不出恰好x块钱时，它不会找零钱给LYK。

LYK知道这个x一定是1~n之间的正整数。当然抠门的LYK只想付给它的仆人恰好x块钱。但LYK只有若干的金币，每个金币都价值一定数量的钱（注意任意两枚金币所代表的钱一定是不同的，且这个钱的个数一定是正整数）。LYK想带最少的金币，使得对于任意x，都能恰好拼出这么多钱。并且LYK想知道有多少携带金币的方案总数。

具体可以看样例。

输入输出格式

输入格式：

第一行一个数n，如题意所示。

输出格式：

输出两个数，第一个数表示LYK至少携带的金币个数，第二数表示方案总数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

3 2

输入样例#2：复制

输出样例#2：复制

4 8

说明

LYK需要至少带3枚金币，有两种方案，分别是{1,2,3}，{1,2,4}来恰好得到任意的1~n之间的x。

数据范围

对于30%的数据n<=10。

对于60%的数据n<=100。

对于100%的数据n<=1000。

题解：

dp求最少金币 dfs求方案数 dp是n^2的

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100009
using namespace std;

int n,ans,gans,cnt;
int dp[maxn],tmp[maxn],f[maxn],use[maxn];

void slove(int x){
    if(!dp[x]){
        ans++;
        for(int i=n;i>=1;i--){
            dp[i]+=dp[i-x];
        }
    }
}

void dfs(int x,int nxt){
    if(x==ans+1){
        int ok=0;
        memset(f,0,sizeof(f));f[0]=1;
        for(int j=1;j<=ans;j++){
            for(int i=n;i>=1;i--)
              f[i]+=f[i-tmp[j]];
        }
        for(int i=1;i<=n;i++) if(!f[i])return;
        cnt++;
        return;
    }
    for(int i=nxt;i<=n;i++){
        if(use[i])continue;
        tmp[x]=i;use[i]=1;
        dfs(x+1,i+1);
        use[i]=0;
    }
}

int main(){

//    freopen("biao.out","w",stdout);
       scanf("%d",&n);
       dp[0]=1;
       for(register int i=1;i<=n;i++)slove(i);
       dfs(1,1);
       printf("%d %d
",ans,cnt);
    return 0;
}

正解：

如果你是财主肯定拿 1 2 4 8 16....

那么最少的金币数量就是log2(n)向下取整+1

那么第二问可以dp或者dfs，因为金币数量最大好像是10....

dp是这样的..

dp[i][j][k]拿了i个金币，和为j，最大值为k的方案数，那么下一次

拿金币的范围是[k+1,j+1].

那么转移为

dp[i+1][j+h][h]+=dp[i][j][k].

第一维可以用滚动掉...不写了。不会

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;

int n;
int dp[20][1024][1024];

int main(){
    scanf("%d",&n);
    int p=(int)(log(n)/log(2)+0.000000001)+1;
    int ans=0;
    dp[1][1][1]=1;//拿个i个数，和为j，最大k
    for(int a=1;a<=p;a++){
        for(int b=1;b<=n;b++){
            for(int c=1;c<=n;c++){
                if(dp[a][b][c]){
                    for(int d=c+1;d<=b+1;d++){
                        dp[a+1][min(b+d,n)][d]+=dp[a][b][c];
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)ans+=dp[p][n][i];
    cout<<p<<" "<<ans<<endl;
    return 0;
}



T3动态规划

题目描述

LYK在学习dp，有一天它看到了一道关于dp的题目。

这个题目是这个样子的：一开始有n个数，一段区间的价值为这段区间相同的数的对数。

我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。我们想

让最终这n个数的价值和尽可能少。例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成

[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。

LYK并不会做，丢给了你。

输入输出格式

输入格式：

第一行两个数n,k。

接下来一行n个数ai表示这n个数。

输出格式：

一个数表示答案。

输入输出样例

输入样例#1：复制

10 2
1 2 1 2 1 2 1 2 1 2

输出样例#1：复制

说明

对于30%的数据n<=10。

对于60%的数据n<=1000。

对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。

其中有30%的数据满足ai完全相同均匀分布在所有数据中。


题解：
对于60%的数据，n^2预处理区间价值，
dp[i][j]表示前i个数分了j段，转移为
dp[i][j]=min{dp[k][j-1]+sum[k+1][j]}
正解：分治优化dp 弃疗。
代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
typedef long long LL;
int c[N],a[N];
LL f[N],g[N];
int p,q,n,k;
LL tot;
void move(int l,int r)  // [p,q]之前的区间
{
    while (l<p) p--,tot+=c[a[p]],c[a[p]]++;
    while (r>q) q++,tot+=c[a[q]],c[a[q]]++;
    while (p<l) c[a[p]]--,tot-=c[a[p]],p++;
    while (r<q) c[a[q]]--,tot-=c[a[q]],q--;
}
void work(int l,int r,int fl,int fr)
//需要求dp[fl] ~ dp[fr]  最优解一定从l~r中的某一个转移过来
{
    if (fl>fr) return;
    int mid=(fl+fr)>>1,mi;
    LL mx=1LL<<60;
    for (int i=l;i<=r;i++)
    if (i<mid)
    {
        move(i+1,mid); -> tot=sum(i+1,mid);
        if (f[i]+tot<mx) mx=f[i]+tot,mi=i;
    }
    g[mid]=mx;
    work(l,mi,fl,mid-1);
    work(mi,r,mid+1,fr);
}
int main()
{
    freopen("dp.in","r",stdin);
    freopen("dp.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    f[0]=0;
    for (int i=1;i<=n;i++) f[i]=1LL<<60;
    while (k--)
    {
        p=1,q=0,tot=0;
        for (int i=1;i<=n;i++) c[i]=0;
        work(0,n-1,1,n);
        for (int i=0;i<=n;i++) f[i]=g[i],g[i]=0;
    }
    cout<<f[n];
    return 0;
}

std


反思：
因为改变读入优化的风格..然后前两个题读不进去数....
打表打半天...结果发现不知什么时候把窗口关了..什么都没打出来..
重新打...十五分钟出来一点点....时间紧张最后很匆忙...
一定把暴力打完..不打玄学暴力...orz