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;
}