HDU - 6655 (杭電多校第七場(chǎng) Just Repeat )卡常題

題意:兩個(gè)人玩游戲:初始時(shí)分別有n和m張牌变过,每張牌有一個(gè)顏色媚狰。你不能出對(duì)面出過的顏色阔拳,沒有牌可以出的失敗。問誰會(huì)贏

題解:想法很簡單辨宠,對(duì)于每一種顏色i嗤形,玩家A有Ai 張牌赋兵,玩家B有Bi張牌叶组,如果玩家A先出了其中的一種的一張牌,那么他就得到了Ai+Bi 的收益帕膜。反之亦然。所以我們按照這個(gè)東西排序之后模擬一遍這個(gè)操作就好了

但是這個(gè)題目由于數(shù)據(jù)出的很大,所以很卡常吞鸭。我們必須選擇常數(shù)小的東西比如避免使用map (事實(shí)上刻剥,unordered_map 也不行)。另外由于很多的數(shù)據(jù)是按照題目給出的偽隨機(jī)數(shù)生成器生成的,所以如果能夠預(yù)先處理掉A和B獨(dú)有的顏色也可以節(jié)約很多時(shí)間

大體來說陶珠,除了排序以外都選用O(n)的操作才可以AC這道題

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define int uint64_t
using namespace std;
using pii = pair<int, int>;
const int maxn = 2e5+10;

int k1, k2;
int rng()
{
    int k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void init_read(pii ma[], int &n, bool gen)
{
    static int tmp[maxn];
    if (gen)
    {
        int mod;
        cin >> k1 >> k2 >> mod;
        for (int i = 0; i < n; i++)
        {
            tmp[i] = rng() % mod;
        }
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            cin >> tmp[i];
        }
    }
    sort(tmp, tmp + n);
    int m = 0;
    for(int i = 0, j = 0; i<n; i = j) {
        for(; (j<n) && (tmp[j] == tmp[i]); ++j);
        ma[m++] = make_pair(tmp[i], int(j - i));
    }
    n = m;
}

auto cmp = [](const pii &p1, const pii &p2) { return p1.first + p1.second > p2.first + p2.second; };

int32_t main()
{
    ios::sync_with_stdio(false);
    int _;
    cin >> _;
    while (_--)
    {
        static pii a[maxn], b[maxn], c[maxn];
        int n, m, p;
        cin >> n >> m >> p;
        init_read(a, n, p == 2);
        init_read(b, m, p == 2);
        
        int sqq = 0, scc = 0, k = 0;
        for (int i = 0, j = 0; i < n || j < m;)
        {
            if ((i < n) && (j < m) && (a[i].first == b[j].first))
            {
                c[k++] = make_pair(a[i++].second, b[j++].second);
            }
            else if (i == n || (j < m && b[j].first < a[i].first))
            {
                scc += b[j++].second;
            }
            else
            {
                sqq += a[i++].second;
            }
        }
        sort(c, c + k, cmp);
        for (int i = 0; i < k; i++)
        {
            if (i & 1)
            {
                scc += c[i].second;
            }
            else
            {
                sqq += c[i].first;
            }
        }
        if (sqq > scc)
        {
            cout << "Cuber QQ" << endl;
        }
        else
        {
            cout << "Quber CC" << endl;
        }
    }
}


?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末寝姿,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子处坪,更是在濱河造成了極大的恐慌玄帕,老刑警劉巖委刘,帶你破解...
    沈念sama閱讀 211,194評(píng)論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件锡移,死亡現(xiàn)場(chǎng)離奇詭異奸汇,居然都是意外死亡擂找,警方通過查閱死者的電腦和手機(jī)贯涎,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,058評(píng)論 2 385
  • 文/潘曉璐 我一進(jìn)店門柬采,熙熙樓的掌柜王于貴愁眉苦臉地迎上來粉捻,“玉大人肩刃,你說我怎么就攤上這事盈包≌柑恚” “怎么了?”我有些...
    開封第一講書人閱讀 156,780評(píng)論 0 346
  • 文/不壞的土叔 我叫張陵蓝角,是天一觀的道長使鹅。 經(jīng)常有香客問我遣钳,道長,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,388評(píng)論 1 283
  • 正文 為了忘掉前任姻成,我火速辦了婚禮,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘垮庐。我一直安慰自己坞琴,他們只是感情好解恰,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,430評(píng)論 5 384
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著紊服,像睡著了一般煎饼。 火紅的嫁衣襯著肌膚如雪马篮。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,764評(píng)論 1 290
  • 那天讹语,我揣著相機(jī)與錄音,去河邊找鬼幅狮。 笑死募强,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的崇摄。 我是一名探鬼主播擎值,決...
    沈念sama閱讀 38,907評(píng)論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼逐抑!你這毒婦竟也來了鸠儿?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,679評(píng)論 0 266
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎进每,沒想到半個(gè)月后汹粤,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,122評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡田晚,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,459評(píng)論 2 325
  • 正文 我和宋清朗相戀三年嘱兼,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片贤徒。...
    茶點(diǎn)故事閱讀 38,605評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡芹壕,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出接奈,到底是詐尸還是另有隱情踢涌,我是刑警寧澤,帶...
    沈念sama閱讀 34,270評(píng)論 4 329
  • 正文 年R本政府宣布序宦,位于F島的核電站睁壁,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏互捌。R本人自食惡果不足惜潘明,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,867評(píng)論 3 312
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望疫剃。 院中可真熱鬧钉疫,春花似錦硼讽、人聲如沸巢价。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,734評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽壤躲。三九已至,卻和暖如春备燃,著一層夾襖步出監(jiān)牢的瞬間碉克,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,961評(píng)論 1 265
  • 我被黑心中介騙來泰國打工并齐, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留漏麦,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,297評(píng)論 2 360
  • 正文 我出身青樓况褪,卻偏偏與公主長得像撕贞,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子测垛,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,472評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容