第一次寒假集訓(xùn)

Problem Description
集訓(xùn)進(jìn)行了將近2個禮拜派哲,這段時間以恢復(fù)性訓(xùn)練為主闽寡,我一直在密切關(guān)注大家的訓(xùn)練情況,目前為止浑彰,對大家的表現(xiàn)相當(dāng)滿意,首先是絕大部分隊員的訓(xùn)練積極性很高拯辙,其次郭变,都很遵守集訓(xùn)紀(jì)律,最后涯保,老隊員也起到了很好的帶頭作用诉濒,這里特別感謝為這次DP專題練習(xí)賽提供題目和測試數(shù)據(jù)的集訓(xùn)隊隊長xhd同學(xué).

特別高興的是,跟隨集訓(xùn)隊訓(xùn)練的一批新隊員表現(xiàn)非常好夕春,進(jìn)步也比較顯著未荒,特別是訓(xùn)練態(tài)度大大超出我的預(yù)期,我敢說及志,如果各位能如此堅持下去片排,絕對前途無量!

考慮到新隊員還沒有經(jīng)過系統(tǒng)訓(xùn)練速侈,我這里特別添加一道簡單題:
給定三個正整數(shù)A率寡,B和C(A,B,C<=1000000),求A^B mod C的結(jié)果.

希望各位都能體會到比賽中AC的快樂倚搬,絕對的量身定制冶共,很高的待遇喲,呵呵...

Input
輸入數(shù)據(jù)首先包含一個正整數(shù)N,表示測試實例的個數(shù)每界,然后是N行數(shù)據(jù)捅僵,每行包括三個正整數(shù)A,B,C。

Output
對每個測試實例請輸出計算后的結(jié)果眨层,每個實例的輸出占一行命咐。

Sample Input
3 2 3 4 3 3 5 4 4 6

Sample Output
0 2 4

考查的是快速冪取模。
ABC數(shù)據(jù)較大谐岁,定義為long long型,數(shù)據(jù)過大,易溢出伊佃,將大數(shù)據(jù)轉(zhuǎn)化為小數(shù)據(jù)窜司,加快運(yùn)算速度。

#include<iostream>
using namespace std;
int main()
{
    int n;
    scanf_s("%d", &n);
    while (n--)
    {
        long long A,B,C;
        cin >> A >> B >> C;
        A = A % C;
        long long h = 1;
        while (B > 0)
        {
            if (B % 2 == 1)
                h = (h*A) %B;
            B = B / 2;
            A = (A*A) % B;
        }
        cout<<h%C;
    }
    return 0;
}

Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".

Input
Line 1: Two space-separated integers: M and N
Lines 2.. M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
Output
Lines 1.. M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
Sample Input
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
Sample Output
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
題意:
牛翻轉(zhuǎn)瓷磚航揉,翻轉(zhuǎn)一塊瓷磚塞祈,這塊瓷磚的上下左右都會翻轉(zhuǎn),求牛最少翻轉(zhuǎn)多少次可以讓瓷磚全是白色帅涂,并輸出翻轉(zhuǎn)次數(shù)最少的情況下對應(yīng)的每塊瓷磚翻轉(zhuǎn)的次數(shù)议薪。
枚舉出每一行瓷磚翻轉(zhuǎn)的情況,求最優(yōu)解媳友。第一行確定了的話第二行也會確定下來斯议,因為第一行某一個的上左右都確定下來了,所以面下也會確定醇锚,所以可以通過第一行推出之后的所有哼御。

#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f //無窮大
int n, m;
int a[20][20];
int f[20][20];
int ans[20][20];

int vx[] = { 0,-1,0,0 };
int vy[] = { 0,0,-1,1 };//瓷磚狀態(tài)

bool check(int x, int y)
{
    return x >= 0 && y >= 0 && x < n && y < m;
}
int get(int x, int y) 
{
    int ret = a[x][y];
    for (int i = 0;i < 4;i++) 
    {
        int tx = x + vx[i];
        int ty = y + vy[i];
        if (check(tx, ty))
            ret += f[tx][ty];
    }

    return ret & 1;
}
int dfs(int k) 
{
    if (k == n - 1) 
    {
        for (int i = 0;i < m;i++)
            if (get(n - 1, i))
                return INF;
        int ret = 0;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
                ret += f[i][j];
        return ret;
    }
    for (int i = 0;i < m;i++)
        f[k + 1][i] = get(k, i);
    return dfs(k + 1);
}
int main() 
{
    cin >> n >> m;;
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            cin>>a[i][j];
    int max = 1 << m;
    int sum = INF;
    memset(ans, 0, sizeof(ans));
    for (int i = 0;i < max;i++)
    {
        int temp = i;
        memset(f, 0, sizeof(f));
        for (int j = m - 1;j >= 0;j--) 
        {
            f[0][j] = temp & 1;
            temp >>= 1;
        }
        int com = dfs(0);
        if (com < sum) 
        {
            sum = com;
            memcpy(ans, f, sizeof(f));
        }
    }
    if (sum == INF)
    {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    for (int i = 0;i < n;i++) 
    {
        cout<<ans[i][0];
        for (int j = 1;j < m;j++)
            cout<< ans[i][j];
        cout<<endl;
    }
    return 0;
}

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111

題意:找出任意一個由0和1組成的數(shù),而且是n的倍數(shù)焊唬。
深度搜索DFS
x * 10,或者x * 10+1,恋昼。

#include<iostream>
#include<cstdio>
using namespace std;
bool f;
int n;
void dfs(unsigned long long x, int n, int k) 
{
    if (f) return;
    if (x%n == 0) 
    {
        cout<<x;
        f = true;
        return;
    }
    if (k == 19) return;
    dfs(x * 10, n, k + 1);
    dfs(x * 10 + 1, n, k + 1);
}

int main()
{
    while (cin>>n) 
    {
        if (n == 0) break;
        f = false;
        dfs(1, n, 0);
    }
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市赶促,隨后出現(xiàn)的幾起案子液肌,更是在濱河造成了極大的恐慌,老刑警劉巖鸥滨,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件嗦哆,死亡現(xiàn)場離奇詭異,居然都是意外死亡爵赵,警方通過查閱死者的電腦和手機(jī)吝秕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來空幻,“玉大人烁峭,你說我怎么就攤上這事★躅酰” “怎么了约郁?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長但两。 經(jīng)常有香客問我鬓梅,道長,這世上最難降的妖魔是什么谨湘? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任绽快,我火速辦了婚禮芥丧,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘坊罢。我一直安慰自己续担,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布活孩。 她就那樣靜靜地躺著物遇,像睡著了一般。 火紅的嫁衣襯著肌膚如雪憾儒。 梳的紋絲不亂的頭發(fā)上询兴,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天,我揣著相機(jī)與錄音起趾,去河邊找鬼诗舰。 笑死,一個胖子當(dāng)著我的面吹牛阳掐,可吹牛的內(nèi)容都是我干的始衅。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼缭保,長吁一口氣:“原來是場噩夢啊……” “哼汛闸!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起艺骂,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤诸老,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后钳恕,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體别伏,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年忧额,在試婚紗的時候發(fā)現(xiàn)自己被綠了厘肮。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡睦番,死狀恐怖类茂,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情托嚣,我是刑警寧澤巩检,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站示启,受9級特大地震影響兢哭,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜夫嗓,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一迟螺、第九天 我趴在偏房一處隱蔽的房頂上張望冲秽。 院中可真熱鬧,春花似錦煮仇、人聲如沸劳跃。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至郑诺,卻和暖如春夹姥,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背辙诞。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工辙售, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人飞涂。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓旦部,卻偏偏與公主長得像,于是被迫代替她去往敵國和親较店。 傳聞我的和親對象是個殘疾皇子士八,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361

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

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,350評論 0 10
  • 夜雨拍打冬的屋檐, 哽咽梁呈、連綿婚度、無所顧忌, 努力以凝結(jié)水的姿態(tài)做最后一次墜落官卡, 急促蝗茁、忘我、酣暢淋漓寻咒。 像一切的自...
    無為何事閱讀 323評論 0 5
  • 圖1: 小椅子是兒子在家坐的小木椅哮翘,因為他屬馬,又活潑好動毛秘,所以聯(lián)想用馬腿置換了椅子腿饭寺;椅子背面3根柱子用了異質(zhì)同...
    若辰讀書閱讀 1,718評論 4 1
  • 一到飯點(diǎn),路面各種小攤都出來了熔脂。感覺好久都沒有經(jīng)歷過在路邊攤買東西吃的時候了佩研,因為現(xiàn)在有了外賣,有了快遞霞揉。是有多久...
    身體棒棒閱讀 171評論 0 4