美团点评CodeM编程大赛|资格赛非官方题解
这是个人题解，不保证和出题人想法一致。官方题解的话，不妨去听2017.06.17晚上红q曾耀辉老师的讲解吧。（逃
Prob A：根据题意实现即可。注意读题，要求连续的子序列。所以只要把A串在B串上，一个个位置比较过去，取最小值作为答案即可。
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
int a[1005],b[1005];
int n,m;
int f[1005];
void get(int* arr,int& x){
scanf("%d",&x);
for(int i=1;i<=x;i++){
scanf("%d",&arr[i]);
}
}
int getans(int* a,int* b,int n){
int ret=0;
for(int i=0;i<n;i++)ret+=(a[i]-b[i])*(a[i]-b[i]);
return ret;
}
int main(){
get(a,n);get(b,m);
int ans=INT_MAX;
for(int i=1;i+n-1<=m;i++){
ans=min(ans,getans(a+1,b+i,n));
}
printf("%d\n",ans);
return 0;
}
Prob B：不需要排序，只需要读入第一个数，然后统计有多少个数>=第一个数，就知道排在倒数第几了。
至于能坚持几轮，最后一名肯定第1轮都过不去，倒数第二名打倒数第一名能挺过去一轮，
倒数第3名的话也只能挺过去一轮——比他弱的2人，一个被他打了，另一个肯定被别人打了，然后这个倒数第三名在下一轮直接出局了。
倒数第4名的话，能做到2轮，以此类推。
显然，n-1个和他一样的/比他弱的+他自己（共n个人），下一轮最多剩下floor(n/2)人。
那就尽量/2，除完之后结果>=1的次数，就是答案。
（或者说，这个排位的二进制表示的最高位，在哪一位。）
#include <stdio.h>
int main(){
int n,f=-11111111,cnt=0,tmp;
for(scanf("%d",&n);n--;){
scanf("%d",&tmp);
if(f==-11111111)f=tmp;
if(tmp<=f)++cnt;
}
int ans=0;
while(cnt>1){
cnt/=2;
++ans;
}
printf("%d\n",ans);
}
Prob C：把问号放到平衡树/set里，记录并维护一下?（问号）出现的下标。
开几个数组，记录手上有几张第x种优惠券，上次买入变成1张是什么时候，上次卖出变成0张是什么时候。
买入的时候，如果之前手里有1张了，那么找出买入上1张后，到现在，中间的最早的？，把这个？改成卖出操作，这样这个买入就合理了。
卖出的时候，之前已经没了的情况处理类似。
（现在看看代码，感觉实现有bug：如果真实记录里，就只有1~10w这10万种优惠券、只有I和O两种操作，不允许空操作的话，那：
I 1 I 2 I 3 ... I 100000 ? O 1 O 2 O 3 ... O 100000
我的程序会觉得没问题，但实际上有：买入10万张以后，这个？不可以再买入，只能随便卖出1张。
但是随便卖出谁，都会导致后面10万条不同的卖出操作中，有谁实际上卖不出去了。
那个问号，要不可以代表任何操作，要不可以是I 100001，不然我的程序是错的……
UPD：根据红q（quailty，http://codeforces.com/profile/quailty ， http://osu.ppy.sh/u/6423914
）的意思，是允许有I 100001，那就没问题了
）
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
int cnt[100005];
int lasto[100005];
int lasti[100005];
int maxid,err;
set<int> left;
char str[2];
int id,m;
int main(){
while(~scanf("%d",&m)){
fill(cnt,cnt+maxid+1,0);
fill(lasto,lasto+maxid+1,0);
fill(lasti,lasti+maxid+1,0);
maxid=0;
err=-1;
left.clear();
for(int i=1;i<=m;i++){
scanf("%s",str);
if(str[0]=='?'){
left.insert(i);
}else{
scanf("%d",&id);
maxid=max(maxid,id);
if(str[0]=='I'){
cnt[id]++;
if(cnt[id]>=2){
auto it=left.lower_bound(lasti[id]);
if(it!=left.end()){
left.erase(it);
--cnt[id];
}else{
if(err==-1)err=i;
}
}
lasti[id]=i;
}else{
cnt[id]--;
if(cnt[id]<0){
auto it=left.lower_bound(lasto[id]);
if(it!=left.end()){
left.erase(it);
++cnt[id];
}else{
if(err==-1)err=i;
}
}
lasto[id]=i;
}
}
}
printf("%d\n",err);
}
return 0;
}
Prob D：有没有解比较，简单：构建反向图（本来是3能到6的，我加一条6到3的边），从n出发，广度优先搜索（bfs）一遍，能到1就有解。 同时记录下哪些点被经过了，这在原图中，就是能到n的点。
有人问了，那什么时候会是无穷长的解？
看下图：
注意我们要字典序最小，而不是长度最小
那么在3这个位置上，我们要不停地选a，而不能选b，否则，字典序上来讲：
aaba......在aaaa.......之后
这里的处理也比较简单：
1、从1出发，每个点贪心选择：如果走a，这个点能到n，那就走a，否则走b。
2、但如果走回到之前走过的点，那说明答案是Infinity。
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
vector<int> G[100005];
int a[100005],b[100005];
int n;
bool vis[100005];
bool vis2[100005];
char str[100005];
void rev_bfs(int p){
queue<int> q;
vis[p]=1;
q.push(p);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<G[x].size();i++){
if(!vis[G[x][i]]){
vis[G[x][i]]=1;
q.push(G[x][i]);
}
}
}
}
void input(int* a){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
int tmp=i+a[i];
if(tmp>=1&&tmp<=n)
G[i+a[i]].push_back(i);
}
}
int main(){
scanf("%d",&n);
input(a);
input(b);
rev_bfs(n);
if(!vis[1]){
puts("No solution!");
return 0;
}
int p=0;
vis2[1]=1;
bool infflag=0;
for(int x=1;x!=n&&!infflag;){
int nxt=x+a[x];
if(nxt>=1&&nxt<=n&&vis[nxt]){
if(!vis2[nxt]){
vis2[nxt]=1;
str[p++]='a';
}else{
infflag=1;
}
x=nxt;
}else{
nxt=x+b[x];
if(nxt>=1&&nxt<=n&&vis[nxt]){
if(!vis2[nxt]){
vis2[nxt]=1;
str[p++]='b';
}else{
infflag=1;
}
}else{
puts("No solution!");
return 0;
}
x=nxt;
}
}
puts(infflag?"Infinity!":str);
return 0;
}
Prob E：
这个问题，经典起手式：求[a,b]的问题，拆成求[1,b]-[1,a-1]的问题，而处理[1,x]的问题一般容易搞定不少。
OK，[1,x]怎么处理？
首先要意识到：在[1,x]中，有约数y的数有x/y个。
那么，假设x为常数，对函数f(y)=x/y，在y=1,2,3...n上的点用曲线近似，是反比例函数在第一象限的图像。
（图就靠大家自己画了~）
特点：前半段很陡峭，差个1，函数值都差远了；后半段很平坦，n/2个数的函数值都为1……
根据这两段的不同情况，我们采取不同的处理策略：
对前半段（比如，1到10万），我们直接算有多少个数包含这个约数x，直接加到答案上。
对后半段（10万以上），我们计算有多少个约数，只有1个、2个....个数的约数中包含他，这些数的取值范围是多少。
然后我们统计出这些约数中，有多少是以1、2、3...9开头的数，乘上相应的约数个数，加到答案中。
这样搞定了~基本是一个sqrt(n)*log(n)的时间复杂度。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef long long ll;
ll a[10],b[10],out[10];
int highest[100001];
void cnt(int l,int r){
memset(out,0,sizeof(out));
char tmp[15];
while(l<=r){
sprintf(tmp,"%d",r);
int t2=tmp[0]-'0';
for(int i=1;tmp[i];i++)t2=t2*10;
if(t2<l)t2=l;
out[tmp[0]-'0']+=r-t2+1;
r=t2-1;
}
}
void get(int x,ll* a){
if(x==0)return;
for(int i=1;i<=100000;i++){
a[highest[i]]+=x/i;
}
if(x<=100000)return;
int last=x;
for(int i=1;;i++){
int p2=x/(i+1);
++p2;
if(p2<=100000)p2=100001;
cnt(p2,last);
for(int j=1;j<=9;j++)a[j]+=out[j]*i;
last=x/(i+1);
if(last<=100000)break;
}
}
int main(){
for(int i=1;i<=9;i++){
for(int j=1;j<=10000;j*=10){
for(int k=0;k<j;k++){
highest[i*j+k]=i;
}
}
}
highest[100000]=1;
int l,r;
scanf("%d%d",&l,&r);
get(r,b);get(l-1,a);
for(int i=1;i<=9;i++)printf("%lld\n",b[i]-a[i]);
}
Prob F:
实现题。开个数组表示棋盘。
3类miss情况，放了子不能再放的miss 1很简单，不赘述。
miss 2，放下去以后自己没气的话，先考虑把对手的、没气的提掉，再检查自己有没有气，没气的话记得还原棋盘。
miss 3，出现重复情况的处理的话，骚年，hash都说得很熟练的话，不妨把这个棋盘也hash起来，用hash来高效查重啊？
反正这题就慢慢写吧~我写+调整了78分钟，红q写+调整了89分钟
（这题有点卡常数，大家要注意自己写出来的代码的效率，我TLE了3发，调了好几下才过……）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_set>
using namespace std;
typedef unsigned int ull;
const int di[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct Point{
int x,y;
Point(int a=0,int b=0):x(a),y(b){}
Point go(int i)const {
return Point(x+di[i][0],y+di[i][1]);
}
bool check()const {
return x>=1&&x<=19&&y>=1&&y<=19;
}
};
struct Board{
int a[21][21];
unordered_set<ull> state;
void init(){
memset(a,0,sizeof(a));
state.clear();
}
void output(){
char tmp[20]="\0";
for(int i=1;i<=19;i++){
for(int j=1;j<=19;j++){
if(a[i][j]==0)
tmp[j-1]='.';
else if(a[i][j]==1)
tmp[j-1]='B';
else if(a[i][j]==2)
tmp[j-1]='W';
}
puts(tmp);
}
}
ull hash(){
ull ans=0;
for(int i=1;i<=19;i++){
for(int j=1;j<=19;j++){
ans*=3;
ans+=a[i][j];
ans%=(int)(1e9+7);
}
}
return ans;
}
int& ref(const Point& p){
return a[p.x][p.y];
}
}board,backup;
bool vis[21][21],vis2[21][21];
bool chi(const Point& p,bool vis[21][21]){
bool alive=false;
int chess=board.ref(p);
queue<Point> q;
q.push(p);
vis[p.x][p.y]=1;
while(!q.empty()){
Point x=q.front();q.pop();
for(int i=0;i<4;i++){
Point y=x.go(i);
if(!y.check())continue;
if(board.ref(y)==0)alive=true;
if(board.ref(y)==chess&&!vis[y.x][y.y]){
vis[y.x][y.y]=1;
q.push(y);
}
}
}
return alive;
}
int put(int type,const Point& p){
int& place=board.ref(p);
if(place!=0) return 1;
backup=board;
place=type;
memset(vis,0,sizeof(vis));
memset(vis2,0,sizeof(vis2));
for(int direct=0;direct<4;direct++){
Point x=p.go(direct);
if(!x.check())continue;
int i=x.x,j=x.y;
if(!vis[i][j] && board.a[i][j]==3-type){
if(!chi(Point(i,j),vis)){
chi(Point(i,j),vis2);
}
}
}
for(int i=1;i<=19;i++){
for(int j=1;j<=19;j++){
if(vis2[i][j]){
board.a[i][j]=0;
}
}
}
if(!chi(p,vis)){
board=backup;
return 2;
}
ull hash_val=board.hash();
unordered_set<ull>::iterator it=board.state.find(hash_val);
if(it!=board.state.end()){
board=backup;
return 3;
}
board.state.insert(hash_val);
return 0;
}
template <class T>
inline void scan(T &ret) {
char c; ret=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
template <class T>
inline void scan_c(T &c) {
while((c=getchar()),!isalnum(c));
}
int main(){
int T,n;
for(scan(T);T--;){
board.init();
for(scan(n);n--;){
char tmp[2];
Point x;
scan_c(tmp[0]);
scan(x.x);scan(x.y);
int ret=put(tmp[0]=='B'?1:2,x);
if(ret){
printf("miss %d\n",ret);
}
}
board.output();
}
return 0;
}
UPD：这份代码在比赛的时候是通过了的。平时练习环境下，要想通过，需要做一些常数优化，比如：
（以下，按缩短的运行时间从多到少排序）
0、提掉没气的对手的子的时候，一个bfs/dfs过去，直接提了，不要像上面的代码一样堆起来，最后清。
1、手写一个数组模拟的循环队列。
STL的queue，底层用了deque，块状数组，非常非常慢！
手写个数组模拟的循环队列，快好多了！
（这个，自己写吧。）
2、在hash()函数内，把ans%=(int)(1e9+7)删掉。
这里写这句，是考虑到，很容易构造hash冲突的例子。http://codeforces.com/blog/entry/4898
但是后来了解到，要hash冲突，串长要挺长的……
3、miss 2类型的情况下，你不需要把整个棋盘还原回去，只要把这个棋子提起来即可。
当然，这个代码还有很多可以做常数优化的空间（应该还能优化出很多吧？），这就靠大家去慢慢折腾了。
0、1、2、3 这4点结合使用，时间基本稳定在1000ms左右。
UPD2：红q曾耀辉的代码真快，150ms。
查看21道真题和解析
