只做了1001 1002 1005 1006。剩下2题可能以后补？
http://acm.hdu.edu.cn/search.php?field=problem&key=2016%22%B0%D9%B6%C8%D6%AE%D0%C7%22+-+%B3%F5%C8%FC%A3%A8Astar+Round2A%A3%A9&source=1&searchmode=source
| Solved | Pro.ID | Title | Author | Source | (AC/Submit)Ratio |
 |
5690 | All X | 2016"百度之星" - 初赛（Astar Round2A） | (438/912)48.03% | |
|
5691 | Sitting in Line | 2016"百度之星" - 初赛（Astar Round2A） | (255/566)45.05% | |
| 5692 | Snacks | 2016"百度之星" - 初赛（Astar Round2A） | (148/689)21.48% | ||
| 5693 | D Game | 2016"百度之星" - 初赛（Astar Round2A） | (70/212)33.02% | ||
|
5694 | BD String | 2016"百度之星" - 初赛（Astar Round2A） | (214/477)44.86% | |
|
5695 | Gym Class | 2016"百度之星" - 初赛（Astar Round2A） | (266/668)39.82% |
题面看不清楚的可以去下面这个比赛网址看，但是交题要去上面这些交。
http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=701
都是题面很明显的中文题，我就不写题意了。
1001 All X
题解：
2种解法：1.矩阵快速幂 2.找循环节。我用的是找循环节。
1.快速幂解法：乘十加一这个操作可以转化为乘上一个2*2的矩阵的操作，用快速幂把一大堆矩阵算完，就无敌了。
2.找循环节，观察MOD数不到1W，所以算着算着肯定会出现重复的数，然后就会循环，我们可以跳过若干循环，直接算最后不到1W步的地方。
设y，循环使y=(y*10+1)%MOD，将每个y记录，a[y] = step。a数组初始化-1，当发现a[y]不为-1时，就循环了。
注意有地方要用long long。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
} const int MAXN=;
const int MAXM=; LL x,k,c;
LL m; LL h[]; bool farm() {
LL y = ;
LL l = ;
MF1(h);
h[] = ;
while(l<m) {
y = y*+x;
y %= k;
l++;
if(h[y]!=-) {
break;
}
h[y] = l;
}
if(l<m) {
LL st = h[y];
LL ed = l;
LL step = ed - st;
LL jump = (m-l)/step;
l += jump*step;
while(l<m) {
y = y*+x;
y %= k;
l++;
}
} return y==c;
} int main() {
int i;
int T,t=;
RD(T);
while(T--) {
cin>>x>>m>>k>>c;
printf("Case #%d:\n",t++);
if(farm())puts("Yes");
else puts("No");
}
return ;
}
1002 Sitting in Line
题解：
状压动规。
注意只有16个数，用了哪些数的状态可以用16位二进制表示。然后想局部最优性，我们可以先算前x个位置放各种数的情况，再推到x+1位置，所需要的信息是第x个是哪个数。
可以设定状态dp[x][y]，x为那个16位二进制，y为已放好的数中最右边那个是什么。
就一顿状态转移。如果已经有数占据一个位置了，就只转移到以这个数结尾的状态。
（可恶，这题我比赛时没想出来，动规苦手）
代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
} const int INF = 0x3f3f3f3f;
const int MAXN=;
const int MAXM=;
const int MM = ; int n;
int a[MAXM],p[MAXM]; int b[<<MAXM][MAXM];
int c[MAXM]; int q[][MM];
int w[][MM];
int qn[];
inline int farm() {
int i,j,k,y;
int now=;
int maxx = <<n;
REP(i,maxx)REP(j,n)b[i][j]=-;
MF1(c);
REP(i,n) {
if(p[i]!=-)c[p[i]]=i;
}
///DP INIT
int st,ed;
if(c[]==-) {
st=;
ed=n-;
} else st=ed=c[]; FOR(i,st,ed) {
y = <<i;
b[y][i] = ;
q[now][qn[now]] = y;
w[now][qn[now]] = i;
qn[now]++;
}
now^=;
int ans=0x80000001;
///DP zhuan yi
FOR(i,,n-) {
int &nn = qn[now];
int &pn = qn[now^];
int st,ed;
if(c[i]!=-) {
st=ed=c[i];
} else {
st=;
ed=n-;
}
nn=;
FOR(j,st,ed) {
y = <<j;
REP(k,pn) {
int &qq =q[now^][k];
int &ww = w[now^][k];
if((qq & y)!=)continue;
// printf("%d, %d:%d, %d:%d\n",i,j,a[j], k,ww);
int z = qq | y;
int newY = b[qq][ww] + a[ww] * a[j];
if(b[z][j]==- || newY > b[z][j]) {
b[z][j]=newY;
// printf("%d,%d,%d\n",z,j,newY);
if(i==n-) ans = max(ans, newY);
q[now][nn] = z;
w[now][nn] = j;
nn++;
}
}
}
now^=;
}
return ans;
} int main() {
int i,x,y;
int L,R;
int T,t=;
RD(T);
while(T--) {
RD(n);
REP(i,n)RD2(a[i],p[i]);
printf("Case #%d:\n",t++);
printf("%d\n",farm());
}
return ;
}
1005 BD String
题解：
疯狂递归。
观察题目，可以发现这个第i个字符串的前半部分其实就是第i-1个字符串。它搞第2^1000个字符串，简直吓人，其实我们只用前面一小部分就行了。
用gank(L,R)递归求区间[L,R]的B数。
观察发现，那个中间的B总是在2的某次方上，我们要以这些B作为分界线。现在先称这些B为“中B”。
要求区间[L,R]，我们找R左边的最右边的一个中B，这个中B，很关键。可以用log2得到。
如果L大于这个中B，我们可以根据规则递归，把区间以中B为轴，镜像到中B的左边。
如果区间包括中B，记得返回值要加1。
如果L小于这个中B，则[中B +1,R]这个区间根据上面的说法，是要镜像到左边的，这样就会和[L, 中B-1]重合，最后发现重合的这一段就抵消掉了（因为镜像到左边是要求D的数量，也就是总数减去B数，减去哦），所以我们只用算不重合的。
这样这个区间就会以log的速度减小，一下就算完了。
（比赛时没做出，没能认真下来思考题，被2^1000吓到了）
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
} const int MAXN=;
const int MAXM=; int a[]; inline LL farm(const LL &l, const LL &r) {
if(l>r)return ;
double lgr = log(r)/log();
int ilgr = floor(lgr );
LL edge = (1LL<<ilgr);
// printf("[%I64d,%I64d],%I64d\n",l,r,edge);
if(l>edge){
return (r-l+) - farm(edge - (r-edge),edge - (l-edge));
}else if(l<edge && r>edge){
LL re = ;
if(r-edge > edge-l){
///re += farm(l,edge-1) + (edge-l+1-1) - farm(l,edge-1);
re += edge-l;
re += farm(edge+(edge-l)+, r);
}else{
///re += (r-edge+1-1) - farm(edge - (r-edge) , edge - 1) + farm(...);
re += r-edge;
re += farm(l, edge - (r-edge) - );
}
return re;
}else if(l==edge){
if(r==edge) return ;
else return (r-edge) - farm(edge - (r-edge),edge - ) + ;
}else if(r==edge){
return farm(l,r-) + ;
}else{
for(int i=;true;i--)
a[i]++;
}
} int main() {
LL L,R;
int T;
RD(T);
while(T--) {
scanf("%I64d%I64d",&L,&R);
printf("%I64d\n",farm(L,R));
}
return ;
}
1006 Gym Class
题解：
贪心。
分析题，首先想把越大的放越前面，但是有人恨他的话，恨他的人要放在更前面。
再一想，也就是有人恨的人，先不能放，先要放没人恨的人。
再一想，放了没人恨的人，它就不会影响到它恨的人，可以把它恨的人的【被恨次数】减一，它恨的人可能就变成没人恨的人。变成了没人恨的人，就有了加入排队的机会。
所以我们就用一个优先队列这样搞就行了。
（我用的是set，比赛时没想清楚就写了，把有人恨的也丢进set了，后来超时，改了一下才过，写题前的思考与规划需要改进）
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
} const int MAXN=;
const int MAXM=; struct Edge {
int y;
int next;
} e[MAXN];
int en;
int head[MAXN]; inline void addEdge(const int &x,const int &y) {
e[en].y = y;
e[en].next = head[x];
head[x] = en;
en++;
} int n,m;
pair<int,int> a[MAXN]; set<int>st;
set<int>::iterator it; inline void del1enemy(const int &x) {
a[x].first--;
if(a[x].first==)st.insert(a[x].second);
} inline LL farm() {
int i,j;
st.clear();
FOR(i,,n) {
if(a[i].first==) st.insert(a[i].second);
}
LL re = ;
int mi = ;
FOR(i,,n) {
it = st.begin();
int x= (*it);
mi = min(mi, -x);
re+=mi;
st.erase(it);
j = head[-x];
while(j!=-) {
del1enemy(e[j].y);
j = e[j].next;
}
}
return re;
} int main() {
int i,x,y;
int T;
RD(T);
FOR(i,,){
a[i].second = -i;
}
while(T--) {
RD2(n,m);
en=;
MF1(head);
FOR(i,,n) {
a[i].first=;
}
REP(i,m) {
RD2(x,y);
addEdge(x,y);
a[y].first++;
}
cout<<farm()<<endl;
}
return ;
}