文档章节

2018 ACM-ICPC 中国大学生程序设计竞赛线上赛

o
 osc_x4h57ch8
发布于 2018/04/23 23:50
字数 928
阅读 8
收藏 0

精选30+云产品,助力企业轻松上云!>>>

2018 ACM-ICPC 中国大学生程序设计竞赛线上赛

[TOC]

A. Death is end

留坑

B.Goldbach

题意

每次给一个偶数$n(n<2<2^{63})$,找出任意两个和为$n$的素数。

分析

从n的$\frac{1}{2}$往两边判素数,使用Miller Rabin随机性素数测试方法。 (ps:自己写了一个虽然过了,但是会被Carmichael数卡掉,还没搞懂板子上的算法怎么搞定Carmichael数的,<font color=red>留坑</font>)

<details><summary> 代码 </summary> ```cpp #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <vector> #include <map> #include <algorithm> using namespace std; typedef long long ll; const ll MOD=1e9+7; const int maxn=1000500; struct Miller_Rabin { int prime[5]={2,3,5,233,331}; ll qmul(ll x,ll y,ll mod){ ll ans=(x*y-(ll)((long double)x/mod*y+1e-3)*mod); ans=(ans%mod+mod)%mod; return ans; } ll qpow(ll x,ll n,ll mod){ ll ans=1; while(n){ if(n&1) ans=qmul(ans,x,mod); x=qmul(x,x,mod); n>>=1; } return ans; } bool isprime_std(ll p) { if(p < 2) return 0; if(p != 2 && p % 2 == 0) return 0; ll s = p - 1; while(! (s & 1)) s >>= 1; for(int i = 0; i < 5; ++i) { if(p == prime[i]) return 1; ll t = s, m = qpow(prime[i], s, p); while(t != p - 1 && m != 1 && m != p - 1) { m = qmul(m, m, p); t <<= 1; } if(m != p - 1 && !(t & 1)) return 0; } return 1; } bool isprime(ll p){ if(p<2||(p!=2&&p%2==0)) return false; for (int i = 0; i < 5; ++i) { if(p==prime[i]) return true; ll t=qpow(prime[i],p-1,p); if(t!=1) return false; } return true; } }mr; int main(int argc, char const *argv[]) { ll x; while(cin>>x){ printf("%d %d\n", mr.isprime(x),mr.isprime_std(x)); } int t; scanf("%d", &t); while(t--){ ll x; scanf("%lld", &x); if(x==4){ printf("2 2\n"); continue; } ll mid=x/2; if(!(mid&1)) mid--; for (ll i = mid; i >= 0; i-=2) { if(mr.isprime_std(i)&&mr.isprime_std(x-i)){ printf("%lld %lld\n", i,x-i); break; } } } return 0; } ``` </details>

C. Heru and his Monitors

又要留坑-_-|||

D. Merchandise

分析

筛选出素数之后,显然同样大小素数不能分在多个组里,否则无法达到最优。 使用$dp[i][j]$表示前$i$个素数分成$j$组的最小总花费,那么可以得到转移方程 $$dp[i][j]=min(dp[k-1][j-1]+(a[i]-a[k])^2), (1<=k<=i)$$ (ps: 强烈谴责计蒜客的数据,交题的时候必须把$0,1$作为素数,否则就会像我一样浪费两天时间)

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int maxn=10500;
const ll inf=0x3f3f3f3f3f3f3f3f;
bool isprime[1<<17];
void get_prime(){
    memset(isprime,true,sizeof isprime);
    // isprime[0]=isprime[1]=false;
    int n=(1<<17);
    for (int i = 2; i < n; ++i)
    {
        if(isprime[i]&&(double)i<=sqrt(n)+1){
            for (int j = i*i; j < n; j+=i)
            {
                isprime[j]=false;
            }
        }
    }
}
ll a[100050],dp[5050][1050];
int q[7050];
double f[7050];
int main(int argc, char const *argv[])
{
    get_prime();
    int t;
    scanf("%d", &t);
    while(t--){
        int r,m;
        scanf("%d%d", &r,&m);
        int n=0;
        for (int i = 0; i < r; ++i)
        {
            int x;
            scanf("%d",&x);
            if(isprime[x]) a[n++]=x;
        }
        sort(a,a+n);
        n=unique(a,a+n)-a;
        for (int i = n; i ; --i)
        {
            a[i]=a[i-1];
        }
        for (int j = 1; j <= m; ++j) dp[0][j]=inf;
        for (int i = 0; i <= n; ++i) dp[i][0]=inf;
        for (int j = 1; j <= m; ++j)
        {
            int h=1,t=0;
            for (int i = 1; i <= n; ++i)
            {
                if(j==1){
                    dp[i][j]=(a[i]-a[1])*(a[i]-a[1]);
                    continue;
                }
                int k=q[t];
                double ff=(double)(dp[i-1][j-1]-dp[k-1][j-1]+a[i]*a[i]-a[k]*a[k])/double(a[i]-a[k]);
                while(t-h+1>=2&&ff<f[t]){
                    t--;
                    k=q[t];
                    ff=(double)(dp[i-1][j-1]-dp[k-1][j-1]+a[i]*a[i]-a[k]*a[k])/double(a[i]-a[k]);
                }
                ++t;
                q[t]=i;
                f[t]=ff;

                while(t-h+1>=2&&(double)2*a[i]>f[h+1]){
                    h++;
                }
                k=q[h];
                dp[i][j]=dp[k-1][j-1]+(a[i]-a[k])*(a[i]-a[k]);
            }
        }
        printf("%lld\n", dp[n][m]);
    }
    return 0;
}

E. Copy and Submit II

太水了略

F. Clever King

$\color{red}{留坑}$

G. Trouble of Tyrant

H. Rock Paper Scissors Lizard Spock

I. Reversion Count

J. Bob's game

K. Ants

L. Nise-Anti-AK Problem

<details> <summary>Click to expand</summary> whatever

html

</details>

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
ICPC程序设计题解系列

ICPC亚洲区域赛题解系列 The 2019 ACM-ICPC China Shannxi Provincial Programming Contest题解 - 海岛Blog - CSDN博客 2019 ICPC中国邀请赛(南昌)暨国际丝绸之路程序设计竞赛-网络赛题解 ...

海岛Blog
04/01
0
0
00 后程序员征战国际,如何拿下计算机领域的奥林匹克?

一个竞赛萌新,如何才能成为世界编程冠军?普通高校学生如何突破 985、211 高校重围?学编程的青少年该如何规划升学路径?打竞赛对于拿大厂 Offer 有多少帮助…… 作者 | 唐小引 头图 | CSDN...

唐门教主
06/22
0
0
ICPC冠军教练亲自授课 字节跳动ICPC冬令营全球招募50支受训队

“2019字节跳动程序设计冬令营”于11月20-28日正式开放网络报名啦! 字节跳动程序设计冬令营是首个由中国企业发起主办,面向全球高校学生,旨在为国际大学生程序设计竞赛(International Col...

AI科技大本营
2018/11/26
0
0
HZNU_TI1050 训练实录

菜鸡队训练实录 比赛记录:[名称:奖项 / 排名] 2018: ZJPSC Bronze / 86 CCPC Jilin Bronze / 95 ICPC Shenyang Bronze / 74 ICPC Tsingdao Honorable / 241 CCPC Finals Bronze / 43 201......

osc_pmwdk963
2018/07/30
5
0
00 后程序员征战国际,如何拿下计算机领域的奥林匹克?

一个竞赛萌新,如何才能成为世界编程冠军?普通高校学生如何突破 985、211 高校重围?学编程的青少年该如何规划升学路径?打竞赛对于拿大厂 Offer 有多少帮助…… 作者 | 唐小引 头图 | CSDN...

CSDN资讯
04/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 01:15 US Supreme Court deems half of Oklahoma a Native American Reservation - (reuters.com) 美国最高法院认为俄克拉荷马州的一半是印第安人保留地 得分:131 | 评...

FalconChen
16分钟前
12
0
OSChina 周五乱弹 —— 求求你吃了我吧,不要再玩弄食物的感情了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @巴拉迪维 :张喆的单曲《陷阱 》 这首歌已经在网易找不到原唱了,不知道被哪家买了版权。#今日歌曲推荐# 《陷阱 》- 张喆 手机党少年们想听歌...

小小编辑
27分钟前
18
1
清华陈文光教授:AI 超算基准测试的最新探索和实践。

道翰天琼认知智能平台为您揭秘新一代人工智能。 无规矩不成方圆。放在超级计算机的研发领域,没有一个大家普遍接受的算力评测指标,便难以推动超算迅猛发展。 而现在伴随着人工智能的发展,大...

jackli2020
42分钟前
7
0
@RequestMapping, consumes 提交简单有意思的测试

getParm @GetMapping("getParm")public Result getParm(String id){ System.out.println(); return ResultFactory.success(id);} 等同于 == bodyParm @PostMapping("bodyParm......

莫库什勒
52分钟前
25
0
63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
今天
46
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部