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 ;
}