Problem Description
集训进行了将近2个礼拜，这段时间以恢复性训练为主，我一直在密切关注大家的训练情况，目前为止，对大家的表现相当满意，首先是绝大部分队员的训练积极性很高，其次，都很遵守集训纪律，最后，老队员也起到了很好的带头作用，这里特别感谢为这次DP专题练习赛提供题目和测试数据的集训队队长xhd同学.
特别高兴的是，跟随集训队训练的一批新队员表现非常好，进步也比较显著，特别是训练态度大大超出我的预期，我敢说，如果各位能如此坚持下去，绝对前途无量！
考虑到新队员还没有经过系统训练，我这里特别添加一道简单题：
给定三个正整数A，B和C（A,B,C<=1000000），求A^B mod C的结果.
希望各位都能体会到比赛中AC的快乐，绝对的量身定制，很高的待遇哟，呵呵...
Input
输入数据首先包含一个正整数N,表示测试实例的个数，然后是N行数据，每行包括三个正整数A,B,C。
Output
对每个测试实例请输出计算后的结果，每个实例的输出占一行。
Sample Input
3 2 3 4 3 3 5 4 4 6
Sample Output
0 2 4
考查的是快速幂取模。
ABC数据较大，定义为long long型，数据过大，易溢出，将大数据转化为小数据，加快运算速度。
#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
题意：
牛翻转瓷砖，翻转一块瓷砖，这块瓷砖的上下左右都会翻转，求牛最少翻转多少次可以让瓷砖全是白色，并输出翻转次数最少的情况下对应的每块瓷砖翻转的次数。
枚举出每一行瓷砖翻转的情况，求最优解。第一行确定了的话第二行也会确定下来，因为第一行某一个的上左右都确定下来了，所以面下也会确定，所以可以通过第一行推出之后的所有。
#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 };//瓷砖状态
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组成的数，而且是n的倍数。
深度搜索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;
}
网友评论