题解 YMOI 2019.6.15

前记

NOIP信心个蛋赛，被各路大佬吊打，信心--

耻辱墙: \(2019.6.15\) \(rank\) \(\color{red}{3}\)

T1 简单队列

题意概述：定义连续的一段单调不递减连续子序列“\(\leq\)”为递增序列，求解最长递增序列的长度\(len\)，和长度\(\geq \lfloor \frac{len}{2}\rfloor\)的递增序列的个数

这个嘛，比较简单

对于子问题1，从头到尾扫一遍

\(num[a]\leq num[a+1]\)，则将第\(a+1\)个数字增添到已有数列上

\(num[a]>num[a+1]\)，则将第\(a\)个数字作为新的递增序列的左端点

对于子问题2，还是扫一遍。注意枚举到第\(i\)位的意义是处理到了以\(i\)作为右端点的递增序列

当前枚举到了\(i\),记录长度为\(size\)

\(num[a]\leq num[a+1]\)，\(size=size+1\)

\(num[a]>num[a+1]\)，\(size=1\)

如过\(size \geq \lfloor \frac{len}{2}\rfloor\),则\(ans+=size - \lfloor \frac{len}{2}\rfloor +1\)

然后，记得特殊处理\(ans=1\)的情况，因为此时\(\lfloor \frac {1}{2} \rfloor=0\)，因此输出答案为\(1\) \(n\)

code:

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAX=1e5+5;

int n; ll num[MAX];

int ans,tar;

ll cnt;

inline int read();

int main(){

    #ifndef ONLINE_JUDGE

    freopen("test.in","r",stdin);

    #else

    freopen("sim.in","r",stdin);

    freopen("sim.out","w",stdout);

    #endif

    n=read();

    for(int i=1;i<=n;++i) cin>>num[i];

    for(int i=1;i<=n;){

    	int u=num[i],p=i,size=1;

    	while(p<n&&num[p+1]>=u){

    		u=num[p+1]; p++; size++;

    	}

    	ans=max(ans,size);

    	i=p+1;

    }

    tar=ans/2;

    if(ans==1){

    	cout<<ans<<" "<<n<<endl;

    	return 0;

    }

    for(int i=1;i<=n;){

    	int u=num[i],p=i,size=1;

    	if(size>=tar){

    		cnt+=(ll)(size+1-tar);

    	}

    	while(p<n&&num[p+1]>=u){

    		u=num[p+1]; p++; size++;

    		if(size>=tar){

    			cnt+=(ll)(size+1-tar);

    		}

    	}

    	i=p+1;

    }

    cout<<ans<<" "<<cnt<<endl;

    return 0;

}

inline int read(){

    char tmp=getchar(); int sum=0; bool flag=false;

    while(tmp<'0'||tmp>'9'){

        if(tmp=='-') flag=true;

        tmp=getchar();

    }

    while(tmp>='0'&&tmp<='9'){

        sum=(sum<<1)+(sum<<3)+tmp-'0';

        tmp=getchar();

    }

    return flag?-sum:sum;

}

T2 简单筛选

题意概述：区间质数和

emm，最烦这种会了就会，不会就完的繁琐小知识点！(╯▔皿▔)╯但既然遇到了就尝试解决一下

这种题目的数据通常是\(l\)和\(r\)都极大，什么筛法都不可能完整筛下来，但是\(r-l\)在可接受范围内。这就让我们注意到区间的重要性

可以发现，对于\(r\)以内的合数，其最小质因数必定\(\leq \sqrt{r}\)，且所有合数都可表示为其最小质因数的倍数。

那么当前处理的区间是\([l,r]\)，我们先处理出来\([2,\sqrt{r}]\)的质数，然后用这些质数枚举倍数，筛掉原区间里的合数

类似埃氏筛的筛法，所以复杂度应该是\(O(n \log n)\)，吧..原谅菜鸡的我并不会严格证明

code:

#include <map>

#include <ctime>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAX=1e5+5;

int prime[MAX]; bool notprime[MAX];

int k,l,r,ans;

clock_t st,ed;

inline int read();

void oula();

int main(){

    #ifndef ONLINE_JUDGE

    freopen("test.in","r",stdin);

    #else

    freopen("sieve.in","r",stdin);

    freopen("sieve.out","w",stdout);

    #endif

    oula();

    cin>>k;

    while(k--){

    	cin>>l>>r; l--;

    	int ansl=0,ansr=0;

    	for(int i=1;i<=prime[0];++i){

    		if(prime[i]>l) break;

    		ansl++;

    	}

    	for(int i=1;i<=prime[0];++i){

    		if(prime[i]>r) break;

    		ansr++;

    	}

    	ans+=(ansr-ansl);

    }

    cout<<ans<<endl;

    return 0;

}

inline int read(){

    char tmp=getchar(); int sum=0; bool flag=false;

    while(tmp<'0'||tmp>'9'){

        if(tmp=='-') flag=true;

        tmp=getchar();

    }

    while(tmp>='0'&&tmp<='9'){

        sum=(sum<<1)+(sum<<3)+tmp-'0';

        tmp=getchar();

    }

    return flag?-sum:sum;

}

void oula(){

	prime[0]=0;

	for(ll i=2;i<=100000;++i){

		if(!notprime[i]) prime[++prime[0]]=i;

		for(int j=1;j<=prime[0]&&i*prime[j]<=100000;++j){

			notprime[prime[j]*i]=true;

			if(i%prime[j]==0) break;

		}

	}

}

T3 简单动规

我是传送门

唯一的难点，怎么判断是否是合法转移

将难点提取概括一下:\(4a+7b\)可以表示哪些数字？

好像正解是用拓展欧几里得来证明的，但我不会会过，但考场忘了这里还是说说在考场也有可能想出来的思路吧


1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28

上图的格子对应下面表格中的数字

\(\color{green}{绿色}\) 代表\(4\)的倍数

\(\color{red}{红色}\) 代表\(7\)的倍数

\(\color{blue}{蓝色}\) 代表\(4\)的倍数佐以\(7\)的倍数，即\(4\)和\(7\)可以表达的所有数字

发现规律，\(4\)和\(7\)表达不出来的最大的数字是\(4\times7-4-7\)

这个规律也可以进一步推广为，\(a\)和\(b\)表达不出来的最大的数字是\(a\times b -a -b\)。虽然对这道题没什么乱用，但可以用之解决NOIP毒瘤真题之小凯的疑惑

code:

#include <map>

#include <ctime>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAX=1e5+5;

struct data{

    int pos,wei;

    bool operator < (const data &x) const{

        return pos<x.pos;

    }

}takala[MAX];

int n,m,ans;

int f[MAX];

bool lawful[18];

inline int read();

void init();

bool check(int);

int main(){

    #ifndef ONLINE_JUDGE

    freopen("test.in","r",stdin);

    #endif

    init();

    n=read(); m=read();

    for(int i=1;i<=n;++i) takala[i].wei=read(),takala[i].pos=read();

    sort(takala+1,takala+1+n);

    int rec,top; rec=0,top=0;

    for(int i=1;i<=n;++i){

        if(!check(takala[i].pos)) continue;

        while(rec<i&&takala[rec+1].pos+17<takala[i].pos){

            rec++; top=max(top,f[rec]);

        }

        for(int j=rec+1;j<=i-1;++j){

            if(!check(takala[i].pos-takala[j].pos)) continue;

            f[i]=max(f[i],f[j]);

        }

        f[i]=max(f[i],top);

        f[i]+=takala[i].wei;

        ans=max(ans,f[i]);

    }

    printf("%d\n",ans);

    return 0;

}

inline int read(){

    char tmp=getchar(); int sum=0; bool flag=false;

    while(tmp<'0'||tmp>'9'){

        if(tmp=='-') flag=true;

        tmp=getchar();

    }

    while(tmp>='0'&&tmp<='9'){

        sum=(sum<<1)+(sum<<3)+tmp-'0';

        tmp=getchar();

    }

    return flag?-sum:sum;

}

void init(){

    for(int k=0;k<=17;++k){

        for(int i=0;i<=7;++i){

            for(int j=0;j<=4;++j){

                if(i*4+j*7==k) lawful[k]=true;

            }

        }

    }

}

bool check(int k){

    if(k>17) return true;

    else return lawful[k];

}

后记

被吊打了~~果然大佬随手用小知识点摸一道题，菜鸡就只能干瞪眼..

一言（ヒトコト）

喜欢你，因为我喜欢你，比地球上任何人都，喜欢你...

——名侦探柯南

巴特西

YMOI 2019.6.15

题解 YMOI 2019.6.15

前记

T1 简单队列

T2 简单筛选

T3 简单动规

后记

最新文章

热门文章