【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（6）

短命女 2022-09-04 01:00 81阅读 0赞

### 文章目录 ###

*  1001 Yes, Prime Minister 思维，数学
 *  1005 Median 思维

题目集地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（6）][2021_MINIEYE_6]  
题目集原地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（6）][2021_MINIEYE_6 1]  
这次我们做出了1001和1005。

# 1001 Yes, Prime Minister 思维，数学 #

题目地址[1001 Yes, Prime Minister][1001 Yes_ Prime Minister]  
题意：给一个数x，找到包含他的最短区间，保证区间和是素数，输出最短区间长度。  
思路：参考博客[\[hdu\] P7025 Yes, Prime Minister][hdu_ P7025 Yes_ Prime Minister]  
AC代码：

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    using namespace std;
    typedef long long ll;
    
    const ll maxn=3e7+1;
    const int leng = 7e7+5;//leng要比maxn大很多，不然筛素数的时候会re,我在这re了好几发。。。。
    
    bool IsPrime[leng];//真值为素数
    ll Prime[leng],ans,tot;
    ll Prime2[leng],top;
    void Choose(ll n) {  //筛选到n
        memset(IsPrime,1,sizeof(IsPrime));//初始化
        //假设每个数为素数
        IsPrime[1]=IsPrime[0]=0;
    
        for(ll i=2; i<=n; i++) { 
            if(IsPrime[i])//如果这个数没筛掉，那么将其加入素数序列
                Prime[++tot]=i;
            for(ll j=1; j<=tot&&i*Prime[j]<=n; j++) { 
                IsPrime[i*Prime[j]]=0;
                if(!i%Prime[j])
                    break;
            }
        }
        for (int i=1; i<=n; i++)//便于找最小的大于x的使2*x+1为素数的值
    		if (IsPrime[2*i+1]) Prime2[++top]=i;
    	return ;
    }
    int main() { 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
        ios::sync_with_stdio(0),cin.tie(0);
        Choose(maxn);//素数筛
    
        int T;
        scanf("%d",&T);
        int x;
        while(T--) { 
            scanf("%d",&x);
            ans = INF;
            if(!x) { 
                cout << 3 << endl;
            }
            else if(x > 0)
            { 
                if(IsPrime[x])
                { 
                    cout << 1 << endl;
                }
                else if(IsPrime[2*x-1]||IsPrime[2*x+1])
                { 
                    cout << 2 << endl;
                }
                else
                { 
                    int pos = upper_bound(Prime + 1,Prime + tot + 1,x) - Prime;//找最小的大于x的质数
                    ans = Prime[pos] * 2;
                    pos = upper_bound(Prime2 + 1,Prime2 + top + 1,x) - Prime2;//找最小的大于2x+1的质数
                    ans = min(ans, 2*Prime2[pos]+1);
                    cout << ans << endl;
                }
            }
            else
            { 
                x = -x;
                int pos = upper_bound(Prime + 1,Prime + tot + 1,x) - Prime;//找最小的大于x的质数
                ans = Prime[pos]*2;
                pos = upper_bound(Prime2 + 1,Prime2 + top + 1,x) - Prime2;//找最小的x使2*x+1是质数
                ans = min(ans,Prime2[pos]*2+1);
                cout << ans << endl;
            }
        }
        return 0;
    }

# 1005 Median 思维 #

题目地址[1005 Median][]  
题意：给n个数1-n，分为m组，每组给定一个中位数，问有没有可能满足给定的中位数。  
思路：首先我们把被m个中位数分割开的数字分成一段一段的：假设  n = 6 , m = 2 , b 1 = 3 , b 2 = 5 n = 6, m = 2, b1 = 3, b2 =5 n=6,m=2,b1=3,b2=5，那么 1 , 2 , ⋅ ⋅ ⋅ , n 1, 2, · · · , n 1,2,⋅⋅⋅,n 这些数会被 \{ 1 , 2 \} \{ 4 \} \{ 6 \} \\\{ 1,2\\\}\\\{ 4\\\} \\\{ 6\\\} \{ 1,2\}\{ 4\}\{ 6\}三段，然后我们会发现任意两段中的任意一对数字一定可以配对消掉  
如果长度最大的段的数字个数小于等于其它段的数字个数之和，那么最终要么全部消掉，要么剩下一个，且剩下的这个数可以在任何一段内。如果会剩下，可以将最后一段的数字剩下最后一个（使得这个剩下的数数值最大），此时再把最后一段的数字放到中位数最小的集合中即可满足题意，所以答案一定为 YES。  
如果长度最大的段的数字个数大于其它段的数字个数之和，那么最终剩下的所有数字都在最大的这段内。设中位数小于这一段的最小值的集合的个数为 x，容易发现当且仅当 x不小于这一段剩下的数字个数时有解。  
我们当时总想着用什么数据结构去解决这个问题了，结果是要自己找规律的。

/* ** Author:skj ** Time:2021-8-5 ** function:1005 */
    #include <bits/stdc++.h>
    const int maxn = 1e5+5;
    using namespace std;
    int a[maxn];
    
    void solve()
    { 
        int n,m;
        scanf("%d%d",&n,&m);
        int len = 0,num = 0;//最长段的长度和最长段的最小的数,比最小的数小的中位数个数
        for(int i = 1;i <= m;i++)
        { 
            scanf("%d",&a[i]);
        }
        sort(a+1,a+m+1);
        if(a[1] > 1)
        { 
            len = a[1] - 1;
        }
        for(int i = 1;i<m;i++)
        { 
            if(len < a[i+1]-a[i]-1)
            { 
                len = a[i+1]-a[i]-1;
                num = i;
            }
        }
        if(a[m] < n)
        { 
            if(len < n - a[m])
            { 
                len = n - a[m];
                num = m;
            }
        }
        if(len <= n-m-len)
        { 
            printf("YES\n");
        }
        else
        { 
            if(num >= 2*len+m-n)
            { 
                printf("YES\n");
            }
            else
            { 
                printf("NO\n");
            }
        }
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t;
    	cin >> t;
    	while(t--)
        { 
            solve();
            memset(a,0,sizeof(a));
        }
        return 0;
    }

[2021_MINIEYE_6]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A86%A3%A9&source=1&searchmode=source
[2021_MINIEYE_6 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=989
[1001 Yes_ Prime Minister]: https://acm.hdu.edu.cn/showproblem.php?pid=7025
[hdu_ P7025 Yes_ Prime Minister]: https://blog.csdn.net/qq_28972011/article/details/119430851
[1005 Median]: https://acm.hdu.edu.cn/showproblem.php?pid=7029