• <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

    智能推薦

    Android中Paint、Canvas的基礎方法用法

    首先paint是畫筆,可以根據paint中的方法設置畫筆的顏色、大小等等屬性,canvas是畫布,用paint畫筆可以在畫布上畫東西 代碼準備: canvas中的方法:(將下面講解的代碼分別放入注釋位置即可使用) 1、繪制單點: 方法:canvas.drawPoint(float x, float y, Paint mPaint); 參數:x:點的x軸位置;y:點的y軸位置;Paint:自定義畫筆...

    十,Future設計模式

    場景介紹 Future模式是多線程開發中非常常見的一種設計模式,它的核心思想是異步調用。這類似我們日常生活中的在線購物流程,帶在購物網看著一件商品時可以提交表單,當訂單完成后就可以在家里等待商品送貨上門。或者說更形象的是我們發送Ajax請求的時候,頁面是異步的進行后臺處理,用戶無需等待請求的結果,可以繼續瀏覽或操作其他內容。 參與角色 Future模式的主要角色有: Main:系統啟動,調用Fut...

    小程序支付系列

      小程序支付,涉及一些知識。 在微信提供的接口文檔中提供了一個微信支付接口,應該是直接調用這個接口就可以發起微信支付 文檔路徑:https://developers.weixin.qq.com/miniprogram/dev/api/api-pay.html#wxrequestpaymentobject          但是,當開始信...

    兩個變量相乘_無廢話學編程基礎(C++篇)3: 變量,賦值語句

    【現實需求】 今天我們要做一個小的應用程序,先說一說需求: 我們日常會去水果店買水果 例如, 蘋果5元/斤 香蕉12元/斤 橘子6元/斤 買完了水果要去結賬了,現在很少看著人手敲計算器了吧。 如果有一個小的應用程序可以解決這個問題不是更好嗎? 要完成這樣一個小的應用程序,需要知道以下幾個基本概念: 順序結構 變量 語句,賦值語句 輸入和輸出 順序結構 首先我們來看一下什么是程序的順序結構。 寫程序...

    wifi放大器速度_放大器的速度有多快?

    wifi放大器速度 AMP has caused quite the stir from a philosophical perspective, but the technology hasn’t received as close of a look. A few weeks ago, Ferdy Christant wrote about the unfair advantage...

    猜你喜歡

    Java IO講解(一)

    Java IO講解 一、簡介 二、Java IO類庫基本架構 三、Java IO類型劃分 四、既然有了字節流,為什么還要有字符流? 五、字節字符相互轉換 一、簡介 IO(輸入輸出)問題是Web應用所面臨的的主要問題這一,因為在當前這個海量數據時代,數據在網絡中隨處流動。在這個數據流動的過程當中都涉及IO問題,大部分應用系統的瓶頸都是IO瓶頸。 二、Java IO類庫基本架構 ①基于字節操作的抽象類...

    部署HPC集群的實施方案

    部署HPC集群的實施方案 濟南友泉軟件有限公司 一、系統配置 1.1 網絡拓撲 1.2 操作系統 登錄節點:CentOS Linux release 7.3.1611 管理節點:CentOS Linux release 7.3.1611 計算節點:CentOS Linux release 7.9.2009, 二、計算節點、登錄節點配置 2.1 域名設置 在登錄節點、所有計算節點上執行以下命令,完成...

    docker基本介紹&docker鏡像&docker常用命令

    1.docker介紹 2.docker鏡像 3.docker常用管命令 4.dockerfile編寫和應用(真實企業應用) 5.docker中網絡部分講解 1.docker介紹 1.什么是docker Docker 是應用最廣泛的開源容器引擎,讓開發者可以打包他們的應用以及依賴包到一個可移植的容器中 docker實質就像虛擬機一樣,就好像是一個具有獨立操作系統的真實機器 虛擬機是有真正的linux...

    oracle ORA-01033

    描述: 操作系統window10 ,Oracle 11g ,電腦異常斷電,再次打開電腦,連接oracle數據庫實例,報錯 Ora-01033 重啟Oracle各項服務,還是無法連接到數據庫 在查找了相關資料后,使用sqlplus命令,用system 登錄 輸入命令 SQL> shutdown normal SQL> startup mount SQL> alter databas...

    vue+vant的Indexbar索引欄的內容加載問題

    vant的IndexBar使用問題 按照官方的寫法引入 前端渣渣第一次使用vant的IndexBar時遇到的問題;根據公司的業務需求,需要做一個移動端的H5demo, 技術選型使用了vue+vant 按照官方的寫法引入 出現了如下錯誤: 只有標題,沒有內容 根據這個問題想出了解決思路: 參考文檔 vant官方文檔里面沒有引入cell這個組件 解決方法: 在這兩個地方加入Cell 這樣就解決了,va...

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