Codeforces Round #194 (Div. 2) 题解
个人体会：
第3场CF，3题。前两题读懂题意都比较简单，第3题列出前几项找下规律就好了。
第4题，当时发现了8个有关联，大概想了下怎么写，刚敲完就没时间了。整体的思路是对的，细节有不少失误。后来也改了好久。
第5题，没看，后来也没想出答案，最后看了别人代码。
1. 呃~~~，觉得自己看CF的题，各种看不明白，看不懂，跟看其他的题目明显感觉不一样。。第二题就看了好久好久才明白题意是什么，恍然大悟，原来这么简单。第三题，到底求的是什么啊~，看了好久好就才明白就是最坏情况下的最少货币。第四题，那个from origorn edge to opposite
edge，一直不知道是什么，棋子放在线上？后来才明白就是走到对面去啊。
edge，一直不知道是什么，棋子放在线上？后来才明白就是走到对面去啊。
2. 心态不够稳，特别是在这种限时竞技的情景下，一旦遇到什么阻碍或者进度有迟缓，就不淡定了。第2题第一次交都没把freopen注释掉。不过学到了这个，oj利器：
#ifndef ONLINE_JUDGE
freopen("test.txt","r",stdin);
#endif
还有表现在第3题，本来慢着性子多推几个就不用WA那么多次了。
3. 思维不够严密，代码能力有待加强。表现在第4题，思路是对的，细节有误，有了思路却不能快速入手去写。
A - Candy Bags
平分糖果
一共有(1+N*N)*N/2个糖果，每个人就是(1+N*N)/2个。对称输出就好了。1-N*N，2-N*N-2，i - (N*N-i+1)。
B - Eight Point Sets
3个横坐标和3个竖坐标能确定9个点，问给出的点是不是9个点中的外面8个。
直接检查，1. 横坐标和纵坐标都只有3个；x1,x2,x3,y1,y2,y3
2. 8个点没有重复的，也都不是中间的那个(x2,y2)。
C - Secrets
用3的倍数的货币去买价值为n的东西，现在已知不能正好支付只能多支付，问最坏的情况下需要支付多少个货币。
手动算出前面一段就可以发现规律，n%3为1、2时，答案是 n/3+1；n%3为0时，答案n/k+1，k是3的倍数且不能被n整除。
D - Chips
在棋盘的四周（除角落）放棋子，在接下来的m-1分钟里，棋子会一步一步地走到对面去。要求：不能掉到陷阱里，不能碰撞，不能交换位置。问最多能放几个。
1. 把陷阱四个方向的位置全挖空，那里肯定不能放。
2. 碰撞出发 --> 每个点，有3个棋子会干扰，就是4个中只能选一个。进一步，发现8个棋子构成一个相互影响的集合，这个集合中能选出4-0个。
枚举每个集合（8个位置），在枚举C(8,4)C(8,3)C(8,2)C(8,1)，累加每个集合中的最大值就是答案。
#include<cstdio>
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#define OP(s) cout<<#s<<"="<<s<<" ";
#define PP(s) cout<<#s<<"="<<s<<endl;
usingnamespace std;
struct node
{
intx,y;
node(){};
node(inta,int b):x(a),y(b){};
}a[10];
staticbool map[1010][1010];
intn,m;
double abs(double a)
{
returna>=0?a:-a;//! 这里忘写了个return ，debug了好久
}
bool ok(node a,node b)
{
if(map[a.x][a.y] || map[b.x][b.y]) return0;
if( (a.x == 1 || a.x == n) && a.y == b.y) return 0;
if( (a.y == 1 || a.y == n) && a.x == b.x) return 0;
if(a.x == b.x || a.y - b.y) return1;
double tmp = abs(a.y - b.y)/abs(a.x - b.x);
double t = abs(tmp -1);
if(abs(tmp - 1) <0.000001) return0;
return1;
}
intg[10];
intmaxv;
voidDFS(int dep,int st)
{
if(dep > 4)
{
maxv =4;
return;
}
for(int i = st;i <= 8;i++) if (!map[a[i].x][a[i].y])//! 这里要加这个条件
{
g[dep] = i;
intj;
for(j = 1;j < dep;j++)
if(!ok(a[g[j]],a[g[dep]])) break;
if(j == dep)
{
maxv = max(maxv,dep);
DFS(dep+1,i+1);
}
}
}
intmain()
{
#ifndef ONLINE_JUDGE
freopen("test.txt","r",stdin);
#endif
cin>>n>>m;
memset(map,0,sizeof(map));
for(int i = 1;i <= m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
map[x][1] = map[x][n] = map[1][y] = map[n][y] = 1;
}
if(n == 2) {cout<<0<<endl;return0;}
intlen = n/2;
intans = 0;
for(int i = 2;i <= len;i++)
{
intj = n-i+1;
a[1] = node(i,1),a[2] = node(j,1);
a[3] = node(n,i),a[4] = node(n,j);
a[5] = node(j,n),a[6] = node(i,n);
a[7] = node(1,j),a[8] = node(1,i);
maxv =0;
DFS(1,1);
ans += maxv;
}
if(n % 2 == 1)
{
intmid = n/2+1;
if(!map[1][mid] || !map[n][mid] || !map[mid][1] || !map[mid][n]) ans++;
}
cout<<ans<<endl;
return0;
}
E - Lucky Tickets
在8个数字间插入*，-，+或者括号，使得表达式的运算结果为k，输出任意的m个。
方法很多，但我没想出来。后来看了别人代码，这里就说下参考代码的思路吧。
假设ans的构成是 [yx] ，y是前4位、x是后4位；y能组合出的值为v[y]、x为v[x]。
先强制使得 v[y] + v[x] = K。再枚举x（1->9999），DFS生成v[x]的集合，然后取
y1 = v[y] = K - v[x]，y2 = v[y] = K+v[x]。排重输出就好了。
y1 = v[y] = K - v[x]，y2 = v[y] = K+v[x]。排重输出就好了。
这个题目比较纠结，我觉得对于任意k组合的数量都是非常大的，所以只要想到一个思路去生成答案的一小部分就好了。
#include<cstdio>
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#define OP(s) cout<<#s<<"="<<s<<" ";
#define PP(s) cout<<#s<<"="<<s<<endl;
usingnamespace std;
vector <int> v[10010];
map<int,bool> mp;
voidDFS(int x)
{
if(v[x].size()) return;
v[x].push_back(x);
for(int bit = 10;bit < x;bit*=10)
{
inta = x%bit,b = x/bit;
DFS(a);DFS(b);
for(int i = 0;i < v[a].size();i++)
for(int j = 0;j < v[b].size();j++)
{
v[x].push_back(v[a][i] + v[b][j]);
v[x].push_back(v[a][i] - v[b][j]);
v[x].push_back(v[b][j] - v[a][i]);
v[x].push_back(v[a][i] * v[b][j]);
}
}
sort(v[x].begin(),v[x].end());
vector<int>::iterator it = unique(v[x].begin(),v[x].end());
v[x].resize(distance(v[x].begin(),it));
}
bool outit(inty,int x)
{
if(y < 0 || y >= 10000) return false;
inttmp = y*10000+x;
if(mp[tmp]) return false;
mp[tmp] =1;
printf("%04d%04d\n",y,x);
return1;
}
intmain()
{
#ifndef ONLINE_JUDGE
freopen("test.txt","r",stdin);
#endif
intK,m;
cin>>K>>m;
for(int x = 1;x < 10000;x++)
{
DFS(x);
for(int i = 0;i < v[x].size();i++)
{
if(outit(K-v[x][i],x)) --m;
if(!m) return 0;
if(v[x][i] && outit(K+v[x][i],x)) --m;
if(!m) return 0;
}
}
}