这次练习的contest地址
http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=17168
本次的题目分别是
A. Super Number
题目大意：
给出n和m，求出一个m位数，使得第i位（n≤i≤m）满足前i位表示的数字是i的倍数；要求这个m位数要尽量小
简单分析：
签到+热身题
DFS即可,可能有时会超时，小优化+拼RP一下吧
#include<stdio.h>
int n,m,a[50];
bool judge(int x)
{
int s=0;
for(int i=0; i<x; i++)
s=(s*10+a[i])%x;
return !s;
}
bool dfs(int x)
{
if(x==m)return 1;
for(int i=0; i<10; i++) {
a[x]=i;
if((x<n-1 || judge(x+1))&& dfs(x+1))return 1;
}
return 0;
}
int main()
{
int T,t;
scanf("%d",&T);
for(t = 0; t < T; ++t) {
int i, found=0;
scanf("%d%d",&n,&m);
for(i=1; i<10; ++i) {
a[0]=i;
if(dfs(1)) {
found=1;
break;
}
}
printf("Case %d: ",t+1);
if(found) {
for(i=0; i<m; ++i) printf("%d",a[i]);
printf("\n");
} else printf("-1\n");
}
return 0;
}
B. Minimum Sum LCM
题目大意：
给定一个N，求出最小共倍数为N的所有不同方案的数中的最小的和。
简单分析：
最小共倍数的任一因子个数和每个数中这个因子个数的最大值相等，让每个数恰巧就是只包含一个因子所有数的和就能保证最小。
注意两种特殊情况：
1、lcm中只有一种因子，比如16
2、lcm为一个素数
#include <cstdio>
#include <cmath>
int main()
{
int n;
int t = 1;
while(scanf("%d",&n) ,n) {
printf("Case %d: ",t++);
int m = sqrt((float)n);
int ans = 0;
int tmpn = n;
int count = 0;
for(int i = 2; i <= m; ++i) {
if(tmpn % i == 0) {
++count;
int tmp = 1;
while(tmpn % i == 0) {
tmp *= i;
tmpn /= i ;
}
ans += tmp;
}
}
if(tmpn == n) printf("%lld\n",(long long)1 + n);
else {
if(tmpn != 1) ans += tmpn;
else if(count == 1) ans++;
printf("%d\n",ans);
}
}
return 0;
}
C. Free Candies
题目大意：
有4堆糖果，每堆有n（最多40）个，有一个篮子，最多装5个糖果，我们每次只能从某一堆糖果里拿出一个糖果，如果篮子里有两个相同的糖果，那么就可以把这两个（一对）糖果放进自己的口袋里，问最多能拿走多少对糖果。糖果种类最多20种.
简单分析：
DP或者记忆化搜索
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=50;
int n,kind[25],data[N][N],map[N][N][N][N];
bool vis[N][N][N][N];
int dp(int,int,int,int);
int tot();
int main()
{
while(scanf("%d",&n)!=EOF) {
if(n==0) break;
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
memset(data,0,sizeof(data));
memset(kind,0,sizeof(kind));
for(int i=0; i<n; i++)
for(int j=0; j<4; j++)
scanf("%d", &data[i][j]);
printf("%d\n",dp(0,0,0,0));
}
return 0;
}
int dp(int a,int b,int c,int d)
{
bool &flag = vis[a][b][c][d];
int &ans = map[a][b][c][d];
if(flag) return ans;
else if (tot() == 5 || (a==n && b==n && c==n && d==n) ) {
flag = 1;
ans = 0;
return 0;
} else {
if(a < n) {
kind[data[a][0]] ^= 1;
ans = max(ans,dp(a+1,b,c,d)+(kind[data[a][0]]==0));
kind[data[a][0]] ^= 1;
}
if(b < n) {
kind[data[b][1]] ^= 1;
ans = max(ans,dp(a,b+1,c,d)+(kind[data[b][1]]==0));
kind[data[b][1]] ^= 1;
}
if(c < n) {
kind[data[c][2]] ^= 1;
ans = max(ans,dp(a,b,c+1,d)+(kind[data[c][2]]==0));
kind[data[c][2]] ^= 1;
}
if(d < n) {
kind[data[d][3]] ^= 1;
ans = max(ans,dp(a,b,c,d+1)+(kind[data[d][3]]==0));
kind[data[d][3]] ^= 1;
}
flag = 1;
return ans;
}
}
int tot()
{
int ret=0;
for(int i=0; i<25; i++) if(kind[i]) ++ret;
return ret;
}
D. S-Trees
题目大意：
可以这样理解：有一排盒子，盒子上标有01，盒子上是一个树结构，m个小球从树顶向下落，遇到0左落遇到1又落，判断有没有落到标记有1的盒子里。
简单分析：
模拟建树，模拟下落。这题就是读题有点小恶，算法很简单。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
struct node {
string name;
char v;
node *left;
node *right;
};
int n, cnt;
string name[1200];
node *newnode(string name)
{
node *u = new node;
u->name = name;
u->right = u->left = NULL;
u->v = '0';
return u;
}
node *build_tree(string name[], int ter, string temp)
{
if(ter == n) {
node *s = newnode(name[ter]);
s -> v = temp[cnt ++];
return s;
} else {
node *s = newnode(name[ter]);
s->left = build_tree(name, ter + 1, temp);
s->right = build_tree(name, ter + 1, temp);
return s;
}
}
char dfs(node *root, string x)
{
node *u = root;
int i;
for(i = 0; i < n; i ++) {
if(x[i] == '0')
u = u->left;
else u = u->right;
}
return u->v;
}
int main()
{
int i, cas = 0;
while(scanf("%d", &n) != EOF && n) {
for(i = 0; i < n; i ++)
cin >> name[i];
string temp;
cin >> temp;
cnt = 0;
node *root = build_tree(name, 0, temp);
cout << "S-Tree #"<< ++cas << ":" << endl;
int m;
scanf("%d", &m);
for(i = 0; i < m; i ++) {
string t;
cin >> t;
cout << dfs(root, t);
}
printf("\n\n");
}
return 0;
}
D. Looploop
题目大意：
题目中定义了六种操作，详见题目，不难理解。
简单分析：
双端队列Dequeue的应用
//转自 http://www.cnblogs.com/shen1000/archive/2012/11/08/2761692.html
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct Root {
deque<int>que1,que2,que3;
int _add;
bool head;
//初始化
void init(int k1,int k2,int n) {
_add=0;
head=true;
while(!que1.empty())que1.pop_back();
while(!que2.empty())que2.pop_back();
while(!que3.empty())que3.pop_back();
int tmp;
for(int i=0; i<k1; i++) {
scanf("%d",&tmp);
que1.push_back(tmp);
}
for(int i=k1; i<k2; i++) {
scanf("%d",&tmp);
que2.push_back(tmp);
}
for(int i=k2; i<n; i++) {
scanf("%d",&tmp);
que3.push_front(tmp);
}
}
//插入一个x,由于是顺时针在指针之后插入
//这样插入之后整就要向顺时针移动一次
//如果que1的第一个在que3中，则只需把x插入que1，然后move(1)即可
void insert(int x) {
if(head) {
que3.push_front(que1.front()+_add);
que1.pop_front();
que1.push_front(x-_add);
} else {
que3.push_front(que1.back()+_add);
que1.pop_back();
que1.push_back(x-_add);
}
move(1);
}
//删除一个元素整体要逆时针移动一次
//那我们就先逆时针移动一次，也就是move(2)
//然后删除que3的ront即可
void _delete() {
move(2);
que3.pop_front();
}
//翻转时只需翻转标记位即可
void reverse() {
head=!head;
}
//加x时只需加延迟标记位即可
void add(int x) {
_add+=x;
}
//移动时比较繁琐，不过思路较简单
//左移相当于逆时针旋转一次
//右移相当于顺时针旋转一次
void move(int x) {
if(x==1) {
if(head) {
que1.push_front(que3.front()-_add);
que3.pop_front();
que2.push_front(que1.back());
que1.pop_back();
que3.push_back(que2.back()+_add);
que2.pop_back();
} else {
que1.push_back(que3.front()-_add);
que3.pop_front();
que2.push_front(que1.front());
que1.pop_front();
que3.push_back(que2.back()+_add);
que2.pop_back();
}
} else {
if(head) {
que3.push_front(que1.front()+_add);
que1.pop_front();
que1.push_back(que2.front());
que2.pop_front();
que2.push_back(que3.back()-_add);
que3.pop_back();
} else {
que3.push_front(que1.back()+_add);
que1.pop_back();
que1.push_front(que2.front());
que2.pop_front();
que2.push_back(que3.back()-_add);
que3.pop_back();
}
}
}
//询问时返回实际值即可
int query() {
if(head) {
return que1.front()+_add;
} else {
return que1.back()+_add;
}
}
} root;
int main()
{
int m,tmp,n,k1,k2;
char op[10];
int ca=1;
while(scanf("%d%d%d%d",&n,&m,&k1,&k2),n) {
root.init(k1,k2,n);
printf("Case #%d:\n",ca++);
while(m--) {
scanf("%s",op);
switch(op[0]) {
case 'a':
scanf("%d",&tmp);
root.add(tmp);
break;
case 'r':
root.reverse();
break;
case 'i':
scanf("%d",&tmp);
root.insert(tmp);
break;
case 'd':
root._delete();
break;
case 'm':
scanf("%d",&tmp);
root.move(tmp);
break;
case 'q':
printf("%d\n",root.query());
break;
}
}
}
return 0;
}
