ABC053

[ABC053C] X: Yet Another Die Game

题面翻译

一个骰子，初始的时候任意的一个面朝上，接下来每一轮可以翻转骰子到相邻的一面，并获得此面的得分（那一面的数值即是得分）。问至少要几轮才可以获得够 $x$ 分。

注：所有数均在$longlong$范围内。

输入格式

一个数 $x$ 。

输出格式

输出也是一个数，即最少的轮数。

题目描述

すぬけくんは $ 6 $ 面サイコロで遊ぶことにしました。サイコロは $ 1 $ から $ 6 $ までの整数がそれぞれの面に書かれており、向かい合う面に書かれた数の和はどれも $ 7 $ です。

すぬけくんはサイコロの好きな面が上向きになるように置いたのち何回か以下の操作を行います。

操作：サイコロを手前、奥、左、右のどれかの方向に $ 90° $ だけ回転させる。その後、上を向いている面に書かれた数を $ y $ として $ y $ 点得る。

例えば、図のように $ 1 $ と書かれた面が上を向いており、手前側の面に $ 5 $ が、右側の面に $ 4 $ が書かれている状況を考えます。
図に示されるように右方向に回転させることで $ 3 $ と書かれた面が上を向くようにすることが可能です。その他、左方向に回転させた場合は $ 4 $ と書かれた面が、手前方向に回転させた場合は $ 2 $ と書かれた面が、奥方向に回転させた場合は $ 5 $ と書かれた面が上を向くようにすることが可能です。

すぬけくんが合計で $ x $ 点以上得るために必要な最小の操作回数を求めなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$ x $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1
7
样例输出 #1
2
样例 #2

样例输入 #2
149696127901
样例输出 #2
27217477801
提示

制約

$ 1 ≦ x ≦ 10^{15} $

$ x $ は整数

思路

被题意误导了，其实大于$x$也是可以的

如果要步骤最少，我们可以6-5-6-5······，这样一路下来，就能得到最小的操作次数。

注意下面的一轮是按6-5算的。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
int main(){
    ios::sync_with_stdio(false);
    ll x;cin>>x;
    //注意这里要乘上2
    ll ans=(x/11)*2;
    
    //如果恰好完成，直接输出即可
    if(x%11==0){
        cout<<ans;
        return 0;
    }
    
    //如果没有，判断是否在0-6之间，如果是则加1
    if(1<=x%11&&x%11<=6){
        ans++;
        cout<<ans;
        return 0;
    }
    
    //否则加2
    cout<<ans+2;
    return 0;
}

[ABC053D] Card Eater

题面翻译

有一堆牌，每张牌上有一个数字。每次可以取出其中3张，丢掉数字最大的和数字最小的牌，把中间那张再放回牌堆。要求最后所有剩余牌上的数字互不相同，求最多能剩几张牌。

题目描述

すぬけくんはカードゲームで遊ぶことにしました。 $ N $ 枚からなるカードの山があり、上から $ i $ 枚目のカードには整数 $ A_i $ が書かれています。

すぬけくんはこのカードの山に対し $ 0 $ 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、$ N $ は奇数であり、少なくとも $ 1 $ 枚のカードを残すことが可能であることが保証されます。

操作：カードの山から任意の $ 3 $ 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード $ 1 $ 枚と最小であるようなカード $ 1 $ 枚の合計 $ 2 $ 枚を選んで食べる。その後残った $ 1 $ 枚をカードの山に戻す。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_{N} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1
5
1 2 1 3 7
样例输出 #1
3
样例 #2

样例输入 #2
15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1
样例输出 #2
7
提示

制約

$ 3 ≦ N ≦ 10^{5} $

$ N $ は奇数

$ 1 ≦ A_i ≦ 10^{5} $

$ A_i $ は整数

Sample Explanation 1

操作を $ 1 $ 回行って $ 1,1,2 $ を取り出すというのが最適な操作手順の $ 1 $ つです。最大値である $ 2 $ と書かれたカードで最小値である $ 1 $ と書かれたカードがそれぞれ $ 1 $ 枚ずつ食べられ、残った $ 1 $ と書かれたカードがカードの山に戻されます。カードの山に残っているカードは $ 1,3,7 $ となり、これらは互いに異なります。

思路

一个很好想的思路，可以统计一下有多少种牌的数量是大于1的（记作$cnt$），这样的话，他们之间就可以两两配对，这样可以避免减少卡牌的种类。

但是有特殊情况，如果$cnt$是奇数，说明会剩下一张重复的卡牌，所以我们不得不重新选出一张牌来解决这个问题。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
map<int,int> m;
map<int,int>::iterator p;
int main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    int ans=0,a=0,cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a;
        //记录重复的卡牌数量
        if(m[a])cnt++;
        else m[a]++;
    }
    //判断是否可能无法配对
    cnt+=cnt%2;
    cout<<n-cnt;
    return 0;
}