2018CCPC吉林训练赛题解

ゝ一世哀愁。 2023-10-11 13:26 28阅读 0赞

00:09:13

solved by hl

打个表发现规律是3个odd,5个even,7个odd,9个even.......

很显然是个等差数列，二分判断项数的奇偶即可

不过似乎大家都有更加简单的方法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

0:26:03

solved by gbs

没有什么好讲的，只有一些细节需要注意。观察可知，当hour为0时,hour输出为12方可符合题目的格式。另外分钟数不足10时前面需要添1个0

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    using namespace std;
    typedef long long LL;
    void outhour(int a)
    {
        if (a==0)
            cout<<12;
        else
            cout<<a;
    }
    void out(int a)
    {
        if (a<10)cout<<"0";
        cout<<a;
    }
    int main()
    {
        int t;
        cin >>t;
        int t1 =1;
        int hour,minute;
        char lls;
        string apm;
        string city1;
        string days;
        map<string,int>map1;
        map1["Beijing"] = 8;
        map1["Washington"] = -5;
        map1["London"] = 0;
        map1["Moscow"] = 3;
        while(t--)
        {
            cin >>hour>>lls>>minute;
            if (hour == 12)
                hour-=12;
            cin >>apm;
            if (apm == "PM")
                hour+=12;
            cin>>city1;
            hour-=map1[city1];
            cin>>city1;
            hour+=map1[city1];
            if (hour <0)
            {
                hour+=24;
                days = "Yesterday";
            }
            else if (hour>=24)
            {
                hour-=24;
                days = "Tomorrow";
            }
            else days = "Today";
            if (hour >= 12)
            {
                hour -= 12;
                apm = "PM";
            }
            else
                apm ="AM";
            printf("Case %d: ",t1++);
            cout<<days<<' ';
            outhour(hour);
            cout<<":";
            out(minute);
            cout<<" ";
            cout<<apm;
            cout<<endl;
    
    
        }
        return 0;
    }

0:43:44

solved by hl

将所有元素从大到小排序，按照两个相同的k并为一个k - 1的方式。

形如哈夫曼树一样维护一个优先队列不断安排上，如果最终可以并为至少两个1存在，就可行，其中一个1的元素全为0组，另一个全为1组

至于怎么确定哪个元素是哪个组的，可以并查集

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    PII a[maxn];
    struct node{
        int id,k;
        node(){}
        node(int id,int k):id(id),k(k){}
        friend bool operator < (node a,node b){
            return a.k < b.k;
        }
    };
    int fa[maxn];
    void init(){
        for(int i = 1; i <= N; i ++) fa[i] = i;
    }
    int find(int x){
        if(x == fa[x] || x < 0) return x;
        return fa[x] = find(fa[x]);
    }
    int main(){
        int T = read();
        int CASE = 1;
        while(T--){
            Sca(N); init();
            priority_queue<node>Q;
            for(int i = 1; i <= N ; i ++){
                Sca(a[i].fi); a[i].se = i;
                Q.push(node(a[i].se,a[i].fi));
            }
            bool flag = 0;
            while(!Q.empty()){
                node u = Q.top(); Q.pop();
                if(!Q.empty() && u.k == Q.top().k){
                    node v = Q.top(); Q.pop();
                    if(u.k == 1){
                        flag = 1;
                        fa[u.id] = -1; fa[v.id] = -2;
                        break;
                    }
                    fa[u.id] = v.id;
                    v.k--;
                //    cout << v.k <<endl;
                    Q.push(v);
                }
            }
            printf("Case %d: ",CASE++);
            if(!flag){
                puts("NO");
                continue;
            }
            puts("YES");
            for(int i = 1; i <= N ; i ++){
                int x = find(i);
                if(x == i || x == -1) printf("1");
                else printf("0");
            }
            puts("");
        }
        return 0;
    }

0:57:47

solved by gbs

dp  
开一个大小为两百的数组dp\[205\],下标为i,表示进行若干局游戏后，当前的(q\*2)是i的概率。对于每一个i,进行一局有 p/100\*i\*2/200的概率结束游戏，把答案加上对应的期望，另外有（1-p/100）的概率让i+3,其余的情况下i+4（i最大为200）。根据当前的情况可以推出下一局游戏时的情况。  
若干局后只有dp\[200\]不为0，那么只要一次胜利，即可成功，期望是前面期望的累计再加上100/q

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    using namespace std;
    typedef long long LL;
    
    double dp[205];
    int main()
    {
        int t;
        int t1= 1;
        int p1;
        cin >>t;
        while(t--)
        {
            cin >>p1;
            for (int i=0; i<205; i++)
                dp[i] = 0;
            dp[4] = 1;
            double win_rate;
            double over_rate;
            double fin_ans = 0;
            for (int times=1;; times++)
            {
                int min_poi =-1;
                for (int i=200; i>=0; i--)
                {
                    if (dp[i] != 0)
                    {
                        min_poi = i;
                        win_rate = dp[i] *p1/100;
                        over_rate = win_rate *i/200;
                        dp[i] -= over_rate;
                        fin_ans += times*over_rate;
                        if (i!= 200)
                        {
                            dp[min(200,i+4)] += win_rate-over_rate;
                            dp[min(200,i+3)] += dp[i] - win_rate + over_rate;
                            dp[i] = 0;
                        }
                    }
                }
                if (min_poi == -1)break;
                if (min_poi == 200)
                {
                    fin_ans += dp[200] *(times + 100.0/p1);
                    break;
                }
            }
            printf("Case %d: %.9f\n",t1++,fin_ans);
    
        }
    
        return 0;
    }

4:07:54

solved by gbs

正解可能是要推公式，但是用三分也可以做。  
对于任意的时间，若0<z<h 那么有令f(x) = 当前截面的圆的半径的平方 - 当前时间下点到圆锥轴线的距离的平方 若f(x)>=0则点在圆锥内 否则 点在圆锥外  
由题意知 点先在圆锥外，后到圆锥内，再然后可能到圆锥外 那么f(x)先<0 后>0, 再然可能<0 第一个f(x) =0的点就是答案  
由于f(x)是两个二次或以下的函数相加，f(x)也必然是二次或以下的函数  
如果f(x)是二次函数，那么用三分可以求出最大值。在时间的下限和这个最大值对应的时间中二分找到f(x)=0的时间即是答案  
如果f(x)是一次函数，直接套用三分也可成功（此时三分的上限就是二分的上限）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    #include<deque>
    using namespace std;
    typedef long long LL;
    const double dis = 1e-9;
    double r,h;
    double cx0,cy0,cz0;
    double vx,vy,vz;
    
    double llx,lly,llz,lltime;
    void find_xyz(double timea)
    {
        lltime = timea;
        llz = cz0 + vz*lltime;
        llx = cx0 + vx*lltime;
        lly = cy0 + vy*lltime;
    }
    inline double find_r2(double z)
    {
        if (h-z<-dis)return 0;
        if (z<-dis)return 0;
        double llr = (h-z)*r/h;
        return llr*llr;
    }
    double jval(double time1)
    {
        find_xyz(time1);
        return find_r2(llz)-llx*llx-lly*lly;
    }
    int main()
    {
        int t;
        int case1 = 1;
        cin >>t;
        while(t--)
        {
            cin >>r>>h;
            cin >>cx0>>cy0>>cz0;
            cin >>vx>>vy>>vz;
            double time1 =0 ;
            double time2 = 10000;
            double the_mid;
            if (vz >0)
            {
                time2 = min(time2,(h-cz0)/vz+ 2*dis);
                time2 = max(time2,time1 + 2*dis);
            }
            else if (vz <0)
            {
                time2 = min(time2,(0-cz0)/vz+ 2*dis);
                time2 = max(time2,time1 + 2*dis);
                if (cz0 >h)
                {
                    time1 = max(time1,(h-cz0)/vz- 2*dis);
                    time1 = min(time1,time2 - 2*dis);
                }
            }
            double t1 =time1;
            double t2 = time2;
            double mid;
            double right1;
            double mval;
            double rval;
            while (t2-t1>dis)
            {
                mid =(t2+t1)/2;
                right1 = (mid + t2)/2;
                mval = jval(mid);
                rval = jval(right1);
                if (mval >rval)
                    t2 = right1;
                else
                    t1 = mid;
            }
            the_mid = t2;
            while(the_mid - time1 >dis)
            {
                mid =(time1+the_mid)/2;
                mval = jval(mid);
                if (mval <0)
                    time1 = mid;
                else
                    the_mid = mid;
            }
            printf("Case %d: %.10f\n",case1++,time1);
    
        }
    
        return 0;
    }

1:32:14

solved by gbs

点i-1必然不能完美收到点i的信号（因为找不到j），但对于点k=i-2以及它左边的点（只要能收到i的信号），只要令j=i-1即可让能收到信号的点k完美收到信号。

说明：  
k点可以完美收到i的信号的条件如下：  
k<i,  
k能收到i的信号，  
且存在k<j<i,使 j到k距离大于等于j到i距离  
且k和i都能收到j的信号、

由题目条件可知，当位于i的点能向左传到k点时，点i-1必然可以向左传到k点时。i和i-1的距离是1，也必然满足距离的条件。因为点i-1能传到k，那么rad至少为2，那么点i-1也可以传到i点。那么所有i能传到且与i距离大于等于2的点都符合条件。

所以对于单个点，答案为max(0,rad-2) 只要把所有答案异或出来即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

04:37:22 （-2）

solved by hl

线段树维护区间和，主要难点在update

每个节点维护一个区间和sum以及一个区间位数和dig

打三个lazy标记，一个维护左边增加的数L，一个维护右边增加的数R，一个维护左右两边增加的数的位数lazydig。

其中位数描述成十的倍数，1位为10,2位为100,3位为1000

那么更新区间和就是sum = sum \* dig + R \* len + L \* dig \* lazydig

其中len为区间长度，除了sum之外其他的比较好维护

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    struct Tree{
        int l,r;
        LL dig,sum,lazydig,L,R;
    }tree[maxn << 2];
    LL ten[maxn];
    inline LL mul(LL a,LL b){
        return a % mod * b % mod;
    }
    inline LL add(LL a,LL b){
        return ((a + b) % mod + mod) % mod;
    }
    void Pushup(int t){
        tree[t].sum = add(tree[t << 1].sum,tree[t << 1 | 1].sum);
        tree[t].dig = add(tree[t << 1].dig,tree[t << 1 | 1].dig);
    }
    void Build(int t,int l,int r){
        tree[t].l = l; tree[t].r = r;
        tree[t].sum = 0; tree[t].dig = tree[t].lazydig = 1;
        tree[t].L = tree[t].R = 0;
        if(l == r) return;
        int m = l + r >> 1;
        Build(t << 1,l,m);
        Build(t << 1 | 1,m + 1,r);
        Pushup(t);
    }
    void change(int t,LL L,LL R,LL dig){
        int len = tree[t].r - tree[t].l + 1;
        tree[t].sum = add(add(mul(tree[t].sum,dig),mul(R,len)),mul(mul(L,dig),tree[t].dig));
        tree[t].dig = mul(tree[t].dig,mul(dig,dig));
        tree[t].L = add(mul(tree[t].lazydig,L),tree[t].L);
        tree[t].R = add(R,mul(tree[t].R,dig));
        tree[t].lazydig = mul(tree[t].lazydig,dig);
    }
    void Pushdown(int t){
        if(tree[t].lazydig != 1){
            change(t << 1,tree[t].L,tree[t].R,tree[t].lazydig);
            change(t << 1 | 1,tree[t].L,tree[t].R,tree[t].lazydig);
            tree[t].L = tree[t].R = 0; tree[t].lazydig = 1;
        }
    }
    void update(int t,int l,int r,LL d){
        if(l <= tree[t].l && tree[t].r <= r){
            change(t,d,d,10);
            return;
        }
        Pushdown(t);
        int m = (tree[t].l + tree[t].r) >> 1;
        if(r <= m) update(t << 1,l,r,d);
        else if(l > m) update(t << 1 | 1,l,r,d);
        else{
            update(t << 1,l,m,d);
            update(t <<1 | 1,m + 1,r,d);
        }
        Pushup(t);
    }
    LL query(int t,int l,int r){
        if(l <= tree[t].l && tree[t].r <= r) return tree[t].sum;
        Pushdown(t);
        int m = (tree[t].l + tree[t].r) >>1;
        if(r <= m) return query(t << 1,l,r);
        else if(l > m) return query(t << 1 | 1,l,r);
        else{
            return add(query(t << 1,l,m),query(t << 1 | 1,m + 1,r));
        }
    }
    int main(){
        int T = read(); ten[0] = 1;
        int CASE = 1;
        for(int i = 1 ; i < maxn; i ++) ten[i] = ten[i - 1] * 10 % mod;
        while(T--){
            Sca2(N,M);
            Build(1,1,N);
            printf("Case %d:\n",CASE++);
            while(M--){
                char op[10];int l,r;
                scanf("%s%d%d",op,&l,&r);
                if(op[0] == 'w'){
                    int d = read();
                    update(1,l,r,d);
                }else{
                    Prl(query(1,l,r));
                }
            }
        }
        return 0;
    }

1:57:45

solved by gbs

贪心  
分为2种方案，一种把对面的怪打完，剩余的怪直接攻击。一种不把对面的怪打完。  
对于第一种情况：按攻击力降序枚举b所拥有的怪物，每次把所有攻击力大于对面的己方怪物加入双端队列。如果对面是防御表示，则派攻击力最低的去攻击，否则派攻击力最高的去攻击。若找不到怪则失败。  
第二种情况：  
首先排除所有防御表示的怪。自己每一次攻击，收益是自己的攻击力-对方攻击力（忽略攻击不足的情况）。若选择攻击k轮，那么收益是自己前k大-对方前k小。所以只需让自己最强的怪攻击对方最弱的怪，直到不能攻击为止。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    #include<deque>
    using namespace std;
    typedef long long LL;
    
    int n,m;
    int an[100005];
    int bn[100005];
    int cn[100005];
    LL sum_atk;
    LL fin_ans;
    void judge1()
    {
        deque<int>stk1;
        int now_p = n-1;
        LL llans =sum_atk;
        for (int i=m-1; i>=0; i--)
        {
            while(now_p>=0)
            {
                if (an[now_p]>bn[i])
                {
                    stk1.push_back(an[now_p]);
                    now_p--;
                }
                else
                {
                    break;
                }
            }
            if (stk1.empty())
                return ;
            if (cn[i] == 1)
            {
                llans -= stk1.back();
                stk1.pop_back();
            }
            else
            {
                llans -= bn[i];
                stk1.pop_front();
            }
        }
        fin_ans = max(fin_ans,llans);
    }
    void judge2()
    {
        int now_n =n-1;
        int now_m =0;
        LL llans = 0;
        while(now_m<m &&now_n>=0)
        {
            if (cn[now_m] ==1)
            {
                now_m++;
                continue;
            }
            if (an[now_n] > bn[now_m])
            {
                llans += an[now_n] - bn[now_m];
                now_n--;
                now_m++;
            }
            else
                break;
        }
        fin_ans = max(fin_ans,llans);
    
    }
    int main()
    {
        int t;
        int t1 = 1;
        cin >>t;
        while(t--)
        {
    
            cin >>n >>m;
            sum_atk = 0;
            for (int i=0; i<n; i++)
            {
                scanf("%d",&an[i]);
                sum_atk += an[i];
            }
    
            for (int i=0; i<m; i++)
                scanf("%d",&bn[i]);
            for (int i=0; i<m; i++)
                scanf("%d",&cn[i]);
            sort(an,an+n);
    
            sort(bn,bn+m);
            fin_ans = 0;
            judge1();
            //cout<<fin_ans<<endl;
            judge2();
            printf("Case %d: %lld\n",t1++,fin_ans);
    
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11289727.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif