• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 【浮*光】洛谷0519五月月賽###全面解析###

    誒,悲慘世界吼...人生如此悲傷...

        我和老大的成績...受傷ing...


    A. 取石子 

    題目:  Alice 和 Bob 在玩游戲。他們有 nn 堆石子,第 i堆石子有 aia_i? 個,保證初始時 ai≤ai+1(1≤i<n)。現在他們輪流對這些石子進行操作,每次操作人可以選擇滿足 ai>ai?1a0? 視為 00)的一堆石子,并從中取走一個。誰最后不能取了誰輸。Alice 先手,他們都使用最優策略,請判斷最后誰會取得勝利。

    分析:最后所有的石子肯定會被選完,而每次每個人選一個,所以石子的總和為奇數則先手贏,否則后手贏。

    #include<bits/stdc++.h>
    using namespace std;
    /* 【取石子】
    他們有 n 堆石子,第i堆石子有 ai個,保證初始時 ai≤ai+1(1≤i<n)
    現在他們輪流對這些石子進行操作,每次操作人可以選擇滿足 ai>ai?1
    ( a0視為 0 )的一堆石子,并從中取走一個。
    誰最后不能取了誰輸。Alice 先手,他們都使用最優策略,請判斷最后誰會取得勝利。*/
    const int maxn=100000009;
    bool okk[maxn];//ai>ai?1
    int a[maxn];
    int main(){
        int n,sum=0; cin>>n;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]); sum+=a[i]%2;//最終都是0
        }
        if(sum%2==0) printf("Bob\n");
        else printf("Alice\n");
        return 0;
    }

    B.偷上網

    題目:Alice 和 Bob 生活在一個 l×l的正方形房子里,由于 Bob 最近沉迷隔膜,Alice 決定要限制 Bob 上網的頻率。

    Alice 建造了n個無線信號屏蔽器,第 i個位于 (xi,yi),屏蔽范圍為 ln 。去尋找一個位置 (x,y)沒有被 Alice 的屏蔽器覆蓋。          

    分析:如果 n=1,則枚舉一下四個角,如果都不可行,一定無解,否則就找到了合法點。

    如果 n≥2,則圓的總面積一定小于正方形的面積,每次隨機一個點,判斷是否可行。顯然隨機次數不會太多就會找到合法解。

    ---> rand有一個最大值是rand_max,用隨機到的數 x/rand_max * 范圍l就行了,

    當前隨機到的占總共的比例乘范圍就是想要的數。

    對于整數來說隨機[x,y]  rand()%(y-x+1)+x;   小數就是[0,range]  ((double)rand()/RAND_MAX)*range

    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    #include<ctime>
    #define delta 1e-6
    using namespace std;
    int n,l;
    bool ok;
    double r;
    struct circle{
        double x,y;
    }pos[11];
    double getdis(double x1,double y1,double x2,double y2){
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    bool judge(double x,double y){
        for(int i=1;i<=n;i++){
    	if(getdis(pos[i].x,pos[i].y,x,y)<r+delta) return false;
        }
        return true;
    }
    int main(){
        srand(time(NULL));
        cin>>n>>l; r=l/n;
        for(int i=1;i<=n;i++)cin>>pos[i].x>>pos[i].y;
        for(int i=1;i<=5000;i++){
    	double nx=((double)rand()/RAND_MAX)*l;
    	double ny=((double)rand()/RAND_MAX)*l;
    	if(judge(nx,ny)){
    	    cout<<nx<<" "<<ny;
    	    return 0;
    	}
        }
        cout<<"GG";
        return 0;
    }  //來自 https://blog.csdn.net/u014296725/article/details/80381654 感謝大佬qwq



    分析:1. 除非起點就是特殊點,要不然不可能會GG。
    2.考慮建邊,對于所有的點,我們向它有可能可以到達的點建邊,邊權就是固定這個骨牌的代價。

    3.因為每一個骨牌都可以連出兩條邊,并且不可能有環,所以是樹;然后就要求最小的代價割掉所有點,考慮樹形DP

    4.設f[x]表示割掉x及其所有字數中的特殊點的最小代價,則

    f[x]=v[fa[x]][x] (if x is a special node)

    f[x]=Σmin(v[x][son[x]],f[son[x]]) ( if x is a common node)

    發現這個建圖可以和DP的過程一起寫成一個類似記搜的方法

    #include<cstdio>
    using namespace std;
    const int N=1005,fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};
    int a[N][N],c[N*N],n,m,k,t,x,y,s_x,s_y;
    bool sp[N][N];
    inline char tc(void){
        static char fl[100000],*A=fl,*B=fl;
        return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
    }
    inline void read(int &x){
        x=0; char ch=tc();
        while (ch<'0'||ch>'9') ch=tc();
        while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
    }
    inline long long min(long long a,long long b){
        return a<b?a:b;
    }
    inline bool check(int x,int y){
        return x>=1&&x<=n&&y>=1&&y<=m;
    }
    inline long long DFS(int x,int y){
        long long ans=0;
        for (register int i=0;i<4;++i){
            int xx=x+fx[i]*2,yy=y+fy[i]*2;
            if (check(xx,yy)&&a[x+fx[i]][y+fy[i]]==a[xx][yy]){
                if (sp[xx][yy]) ans+=c[a[xx][yy]]; 
                else ans+=min(DFS(xx,yy),c[a[xx][yy]]);
            }
        }
        return ans;
    }
    int main(){
        register int i,j;
        read(n); read(m); read(k); t=n*m-1>>1;
        for (i=1;i<=t;++i)
        read(c[i]);
        for (i=1;i<=k;++i)
        read(x),read(y),sp[x][y]=1;
        for (i=1;i<=n;++i)
        for (j=1;j<=m;++j){
            read(a[i][j]);
            if(!a[i][j]) s_x=i,s_y=j;
        }
        if (sp[s_x][s_y]) puts("GG"); 
        else printf("%lld",DFS(s_x,s_y));
        return 0;
    } //來自 https://www.cnblogs.com/cjjsb/p/9076443.html 膜拜dalao




                                                                                    ——時間劃過風的軌跡,那個少年,還在等你。
    版權聲明:本文為flora715原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/flora715/article/details/80378699

    智能推薦

    神奇的Batch Normalization 如果一個模型僅訓練BN層會是什么樣的

    您可能會感到驚訝,但這是有效的。 ? 最近,我閱讀了arXiv平臺上的Jonathan Frankle,David J. Schwab和Ari S. Morcos撰寫的論文“Training BatchNorm and Only BatchNorm: On the Expressive Power of Random Features in CNNs”。 這個主意立刻引起了...

    用Python實現校園通知更新提醒

    前言 這個項目實已經在一個月前已經完成了,一直都想寫一篇博客來總結這個過程中遇到的一些問題。但最近一個月來都比較忙,所以一直拖到了現在。 首先說說起因吧,我沒事的時候,總喜歡依次點開學校主頁、教務處、圖書館以及學院的網站,看看有沒有什么新通知,雖然大多與我無關。恰逢最近正在學Python,經常聽到別人說用Python寫爬蟲很簡單,但自己尚未接觸過爬蟲。于是抱著試一試的心態看了幾篇關于Python爬...

    spring_ioc相關_第一章

    1 spring是一站式框架,在javaee的三層結構中,每一層都提供不提并的解決技術 web層:springMVC service層:spring的ioc dao層:spring的jdbcTemplate 2 javaee為避免兩個類之間出現耦合,則把對象的創建交給spring進行管理,spring的ioc操作:(1)ioc的配置文件方式;(2)ioc注解方式 3 ioc的底層原理使用技術(1)...

    【Python+OpenCV】視頻流局部區域像素值處理-一種特征提取方法

    參考我之前寫的處理圖片的文章:Python+OpenCV實現【圖片】局部區域像素值處理(改進版) 開發環境:Python3.6.0 + OpenCV3.2.0 任務目標:攝像頭采集圖像(例如:480*640),并對視頻流每一幀(灰度圖)特定矩形區域(480*30)像素值進行行求和,得到一個480*1的數組,用這480個數據繪制條形圖,即在逐幀采集視頻流并處理后“實時”顯示采...

    JavaWeb——【前端】——注冊頁面

    頁面效果 實現代碼 注意事項 主要使用的bootstrap樣式 如果想引用,不要直接復制,沒用的。 先介紹下所引用的文件: boostrap的js、bootstrap的css、jquery的js、以及自己編寫的register.css。 因為博主用的thymeleaf語法,所以有th符號。 若要使用時,根據個人情況導入相應的依賴。...

    猜你喜歡

    網站HTTP升級HTTPS完全配置手冊

    本文由葡萄城技術團隊于博客園原創并首發 轉載請注明出處:葡萄城官網,葡萄城為開發者提供專業的開發工具、解決方案和服務,賦能開發者。 今天,所有使用Google Chrome穩定版的用戶迎來了v68正式版首個版本的發布,詳細版本號為v68.0.3440.75,上一個正式版v67.0.3396.99發布于6月13日,自Chrome 68起,當在加載非HTTPS站點時,都會在地址欄上明確標記為&ldqu...

    echarts 自定義儀表盤設置背景圖片

    echarts儀表盤 使用插件 vue-echarts 代碼示例 HTML部分 js部分 效果圖...

    RT-Thread Studio部分定時器時鐘不正確的解決方案

    在昨天的RT-Thread Studio硬件定時器hwtimer在stm32f411上的使用筆記中,遇到了部分定時器速度想象中和實際不一致的情況,具體表現在定時器2、3、4、5、9、10、11都正常,但定時器1要快一倍。 仔細查看代碼,找到了原因。 因為代碼使用的是工程是直接生成的時鐘代碼,實際的時鐘頻率是這樣的: 而實際的定時器時鐘配置代碼如下: 針對F411,去掉其中的宏定義是這樣的: 這里說...

    symfony學習筆記之模板渲染-----twig總結

    參考:https://blog.csdn.net/liebert/article/details/77414217 目錄 一、模板引擎工作原理 二、Twig模板引擎 1.運行環境要求 2.基本API用法 3.設計模板 (1)變量輸出         a.全局變量         b.設置變量 (2)...

    小甲魚Python3學習筆記之第六講(僅記錄學習)

    第六講:python之常用操作符 一、知識點: 0.算術運算符:+,-,*,/,%(取模,即求余數),**(冪運算),//(地板除法,取整除,返回商的整數部分) 備注:①雙斜杠 // 除法總是向下取整。             ②從符點數到整數的轉換可能會舍入也可能截斷,建議使用math....

    精品国产乱码久久久久久蜜桃不卡