1001 All X
Problem Description：
F(x,m) 代表一个全是由数字x组成的m位数字。请计算，以下式子是否成立：
F(x,m) mod k ≡ c
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=(<<)-;
int main()
{
int T,Case=;
scanf("%d",&T);
while(T--)
{
printf("Case #%d:\n",++Case);
int x,k,c;
LL m;
scanf("%d%lld%d%d",&x,&m,&k,&c);
m%=k;
LL mod1=;
LL tmp=x;
--m;
while(m--)
{
mod1*=;
mod1%=k;
tmp+=(x%k*(mod1)%k)%k;
tmp%=k;
}
if(tmp==c) printf("Yes\n");
else printf("No\n");
}
return ;
}
1002 Sitting in Line
Problem Description：
度度熊是他同时代中最伟大的数学家，一切数字都要听命于他。
现在，又到了度度熊和他的数字仆人们玩排排坐游戏的时候了。
游戏的规则十分简单，参与游戏的N个整数将会做成一排，
他们将通过不断交换自己的位置，最终达到所有相邻两数乘积的和最大的目的，
参与游戏的数字有整数也有负数。
度度熊为了在他的数字仆人面前展现他的权威，他规定某些数字只能在坐固定的位置上，
没有被度度熊限制的数字则可以自由地交换位置。
状压DP
就是枚举放的顺序
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<conio.h>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=(<<)-;
int A[],p[],c[<<];
int dp[<<][];
int Count(int x)
{
int res=;
while(x)
{
if(x%) res++;
x/=;
}
return res;
}
int main()
{
for(int i=;i<<<;++i) c[i]=Count(i);
int T,Case=;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=;i<<<;++i)
for(int j=;j<=n;++j)
dp[i][j]=-inf;
for(int i=;i<n;++i) scanf("%d%d",&A[i],&p[i]);
A[n]=;
dp[][n]=;
for(int i=;i<<<n;++i)
{
for(int j=;j<=n;++j)
if(dp[i][j]!=-inf)
{
for(int k=;k<n;++k)
if(((i&<<k)==)&&(p[k]==-||p[k]==c[i]))
{
dp[i|(<<k)][k]=max(dp[i|(<<k)][k],dp[i][j]+A[j]*A[k]);
}
}
}
int ans=-inf;
for(int i=;i<=n;++i)
ans=max(ans,dp[(<<n)-][i]);
printf("Case #%d:\n",++Case);
printf("%d\n",ans);
}
return ;
}
1003 Snacks
Problem Description:
百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。
每个零食机都有一个值v，表示为小度熊提供零食的价值。
由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。
小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。
另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。
为小度熊规划一个路线，使得路线上的价值总和最大。
DFS序
线段树里每个节点保存的是从根节点与当前节点子树路径和的最大值…很奇妙
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=(<<)-;
int A[maxn];
struct node
{
int next,to;
}e[maxn*];
int h[maxn],tot;
void add_edge(int a,int b)
{
e[++tot].next=h[a];
e[tot].to=b;
h[a]=tot;
}
int In[maxn*],Out[maxn*],tim,Rank[maxn*],Fa[maxn];
void dfs(int u,int fa)
{
Fa[u]=fa;
In[u]=++tim;
Rank[tim]=u;
for(int i=h[u];~i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa)
{
dfs(v,u);
}
}
Out[u]=tim;
}
//Graph--------------------------------
struct Segment
{
LL Max,lazy;
}tree[maxn*];
void build(int l,int r,int rt)
{
tree[rt].lazy=;tree[rt].Max=;
if(l==r) return ;
int mid=(l+r)/;
build(l,mid,rt*);
build(mid+,r,rt*+);
}
void fun_Push_down(int rt,int rt1)
{
tree[rt1].Max+=tree[rt].lazy;
tree[rt1].lazy+=tree[rt].lazy;
}
void Push_down(int rt)
{
if(tree[rt].lazy)
{
fun_Push_down(rt,rt*);
fun_Push_down(rt,rt*+);
tree[rt].lazy=;
}
}
void Push_up(int rt)
{
tree[rt].Max=max(tree[rt*].Max,tree[rt*+].Max);
}
void Update(int left,int right,int l,int r,int rt,int x)
{
if(left<=l&&r<=right)
{
tree[rt].lazy+=x;
tree[rt].Max+=x;
return ;
}
Push_down(rt);
int mid=(l+r)/;
if(left<=mid)
Update(left,right,l,mid,rt*,x);
if(right>mid)
Update(left,right,mid+,r,rt*+,x);
Push_up(rt);
}
LL Query(int left,int right,int l,int r,int rt)
{
if(left<=l&&r<=right) return tree[rt].Max;
Push_down(rt);
int mid=(l+r)/;
if(right<=mid)
return Query(left,right,l,mid,rt*);
else if(left>mid)
return Query(left,right,mid+,r,rt*+);
else
{
LL tmp=Query(left,right,l,mid,rt*);
tmp=max(tmp,Query(left,right,mid+,r,rt*+));
return tmp;
}
}
//Segment------------------------------
LL get_dis_root(int u)
{
if(Fa[u]==) return ;
LL tmp=;
tmp+=A[Fa[u]];
return tmp+get_dis_root(Fa[u]);
}
int main()
{
int T,Case=;
scanf("%d",&T);
while(T--)
{
memset(h,-,sizeof(h));
tim=tot=;
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<n;++i)
{
int u,v;
scanf("%d%d",&u,&v);
++u,++v;
add_edge(u,v);add_edge(v,u);
}
for(int i=;i<=n;++i) scanf("%d",&A[i]);
dfs(,-);
build(,n,);
for(int i=;i<=n;++i)
Update(In[i],Out[i],,n,,A[i]);
printf("Case #%d:\n",++Case);
while(m--)
{
int ope,x;
scanf("%d%d",&ope,&x);
++x;
if(ope==)
{
int y;
scanf("%d",&y);
Update(In[x],Out[x],,tim,,y-A[x]);
A[x]=y;
}
else
{
LL ans=;
ans+=Query(In[x],Out[x],,tim,);
printf("%lld\n",ans);
}
}
}
return ;
}
1004 D Game
Problem Description
众所周知，度度熊喜欢的字符只有两个：B 和D。
今天，它发明了一个游戏：D游戏。
度度熊的英文并不是很高明，所以这里的D，没什么高深的含义，只是代指等差数列(等差数列百科)中的公差D。
这个游戏是这样的，首先度度熊拥有一个公差集合{D}{D}，然后它依次写下NN个数字排成一行。游戏规则很简单：
在当前剩下的有序数组中选择X (X \geq )X(X≥) 个连续数字；
检查选择的XX个数字是否构成等差数列，且公差 d\in {D}d∈{D}；
如果满足，可以在数组中删除这XX个数字；
重复 - − 步，直到无法删除更多数字。
度度熊最多能删掉多少个数字，如果它足够聪明的话？
区间DP
有两种合并方式
1.[l,i]-[i+1,r]合并
2.跨区间合并,但是我们每次跨区间左右两边一共只要两个和三个,更多的可以通过区间DP的特性来完成，这样就每次记忆化搜索的时候就可以O(N)了
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=+;
int dp[maxn][maxn],A[maxn];
map<int,bool>Map;
int dfs(int l,int r)
{
if(dp[l][r]!=-inf) return dp[l][r];
if(l==r) return ;
if(l+==r)
{
if(Map[A[r]-A[l]]) return ;
return ;
}
int tmp=;
if(Map[A[r]-A[l]]&&dfs(l+,r-)==(r--l)) tmp=r-l+;
if(A[r-]-A[l]==A[r]-A[r-]&&Map[A[r-]-A[l]]&&dfs(l+,r-)==(r--l)) tmp=r-l+;
if(A[l+]-A[l]==A[r]-A[l+]&&Map[A[l+]-A[l]]&&dfs(l+,r-)==(r--l)) tmp=r-l+;
for(int i=l;i<r;++i)
tmp=max(tmp,dfs(l,i)+dfs(i+,r));
dp[l][r]=tmp;
return tmp;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
Map.clear();
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
dp[i][j]=-inf;
for(int i=;i<=n;++i) scanf("%d",&A[i]);
for(int i=;i<=m;++i)
{
int x;
scanf("%d",&x);
Map[x]=true;
}
printf("%d\n",dfs(,n));
}
return ;
}
1005 BD String
Problem Description
众所周知，度度熊喜欢的字符只有两个：B和D。
今天，它发明了一种用B和D组成字符串的规则：
S(1)=BS(1)=B
S(2)=BBDS(2)=BBD
S(3)=BBDBBDDS(3)=BBDBBDD
…
S(n)=S(n-1)+B+reverse(flip(S(n-1))S(n)=S(n−1)+B+reverse(flip(S(n−1))
其中，reverse(s)reverse(s)指将字符串翻转，比如reverse(BBD)=DBBreverse(BBD)=DBB，flip(s)flip(s)指将字符串中的BB替换为DD，DD替换为BB，比如flip(BBD)=DDBflip(BBD)=DDB。
虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，
目前它已经算出了S(2^{1000})S(2^1000)的内容，但度度熊毕竟只是只熊，
一次读不完这么长的字符串。
它现在想知道，这个字符串的第LL位（从1开始）到第RR位，含有的BB的个数是多少？
就是通过迭代来完成规律
先尽可能枚举我们已知的情况来加速，然后每次因为每次反转是有规律的
串A翻转完B的个数-D的个数==1,通过这个特性我们可以来缩小每个大于len到小于len的长度来迭代
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=(<<)-;
LL len[maxn],A[maxn];
void init()
{
len[]=;A[]=;
for(int i=;i<maxn;++i)
{
len[i]=len[i-]*+;
A[i]=len[i-]+;
}
}
LL solve(LL x)
{
if(x==) return ;
int k=;
while(k<maxn&&len[k]<=x) ++k;
--k;
if(len[k]==x) return A[k];
else
return solve(*len[k]-x+)+x-len[k];
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
LL l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",solve(r)-solve(l-));
}
return ;
}
1006 Gym Class
Problem Description
众所周知，度度熊喜欢各类体育活动。
今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。
在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到NN，
在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，
作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，
在满足这个前提的情况下，新晋体育课老师——度度熊，
希望最后的排队结果可以使得所有同学的评价分数和最大。
topsort+优先队列就OK了
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=(<<)-;
struct node
{
int val;
bool friend operator<(node u,node v)
{
return u.val<v.val;
}
node(int a=)
{
val=a;
}
};
priority_queue<node>q;
vector<int>vec[maxn];
int top[maxn];
int A[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
memset(top,,sizeof(top));
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) vec[i].clear();
for(int i=;i<=m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
vec[u].push_back(v);
top[v]++;
}
while(!q.empty()) q.pop();
for(int i=;i<=n;++i)
if(top[i]==) q.push(node(i));
int len=;
while(!q.empty())
{
node cur=q.top();
q.pop();
int x=cur.val;
A[++len]=x;
int Size=vec[x].size();
for(int i=;i<Size;++i)
{
top[vec[x][i]]--;
if(top[vec[x][i]]==) q.push(node(vec[x][i]));
}
}
int Max=inf;
LL Sum=;
for(int i=;i<=len;++i)
{
Max=min(Max,A[i]);
Sum+=Max;
}
printf("%lld\n",Sum);
}
return ;
}