2016百度之星 初赛2A ABEF

时间:2022-07-27 13:06:05

只做了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
2016百度之星 初赛2A ABEF 5690 All X   2016"百度之星" - 初赛(Astar Round2A) (438/912)48.03%
2016百度之星 初赛2A ABEF 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%
2016百度之星 初赛2A ABEF 5694 BD String   2016"百度之星" - 初赛(Astar Round2A) (214/477)44.86%
2016百度之星 初赛2A ABEF 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 ;
}