NOIP2014複賽提高組day1(A:生活大爆炸版石頭剪刀布 B:聯合權值 C:飛揚的小鳥)

NO IMAGE

A題:
正宗水題——RPS
隨便搞搞就好了,
我也想不出來這題還能有什麼思路。。。

#include<stdio.h>
#define M 205
int A[M],B[M]; 
int mark[15][15];
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int main(){
mark[0][0]=0;mark[0][1]=-1;mark[0][2]=1;mark[0][3]=1;mark[0][4]=-1;//純模擬
mark[1][0]=1;mark[1][1]=0;mark[1][2]=-1;mark[1][3]=1;mark[1][4]=-1;
mark[2][0]=-1;mark[2][1]=1;mark[2][2]=0;mark[2][3]=-1;mark[2][4]=1;
mark[3][0]=-1;mark[3][1]=-1;mark[3][2]=1;mark[3][3]=0;mark[3][4]=1;
mark[4][0]=1;mark[4][1]=1;mark[4][2]=-1;mark[4][3]=-1;mark[4][4]=0;
int n,a,b;
scanf("%d %d %d",&n,&a,&b);
for(int i=1;i<=a;i  )scanf("%d",&A[i]);
for(int i=1;i<=b;i  )scanf("%d",&B[i]);
int m=a*b/gcd(a,b);
if(n<=m){
int ans1=0,ans2=0;
for(int i=1;i<=n;i  ){
int x=i%a,y=i%b;
if(!x)x =a;
if(!y)y =b;
if(mark[A[x]][B[y]]==1)ans1  ;
else if(mark[A[x]][B[y]]==-1)ans2  ;
}printf("%d %d\n",ans1,ans2);
}else{
int tmp1=0,tmp2=0;
for(int i=1;i<=m;i  ){
int x=i%a,y=i%b;
if(!x)x =a;
if(!y)y =b;
if(mark[A[x]][B[y]]==1)tmp1  ;
else if(mark[A[x]][B[y]]==-1)tmp2  ;
}int ans1=n/m*tmp1,ans2=n/m*tmp2;
n%=m;
for(int i=1;i<=n;i  ){
int x=i%a,y=i%b;
if(!x)x =a;
if(!y)y =b;
if(mark[A[x]][B[y]]==1)ans1  ;
else if(mark[A[x]][B[y]]==-1)ans2  ;
}printf("%d %d\n",ans1,ans2);
}return 0;
}

B題:
其實這題還不錯
聽對面的Kanosword大神和Songty大神說還有樹形dp的寫法,
然而我並搞不懂怎麼dp。。。
在這裡講解一下我的思路
我們知道距離為二的兩點要麼是是這個數與他的祖父,要麼由他的各個兒子組成
然而經過思考我們會發現,
這個數和他的祖父這個情況可以說沒有任何意義
因為當我們遞迴到某一個數時,可以把他的父親和他的兒子放在一起進行組合,
於是乎就變成了這樣一個問題
對於樹上的每一個點x
用他的父親節點和子節點所構成的集合中的數兩兩聯合,
而後求出這樣配對所得的權值的最大值和總和【%10007】//PSPS:最大值無須mod
於是乎當我們直接暴力的時候
會發現複雜度最壞情況下是O(n2n^2)的
若某一組資料這棵樹只有兩層,顯然會TLE
但顯然求最大值是不會TLE的
於是我們來思考怎麼優化求總和
我們把之前說到的那個集合中的數表示為aia_i
我們用sumisum_i來表示從點i出發的所有路勁的聯合權值之和
為了表示方便我們把與點x距離為1的點的集合的大小表示為m,下標分別為1~m
於是乎
sumisum_i
=ai⋅(a1 a2 … ai−1 … ai 1 … am−1 … am)=a_i·(a_1 a_2 … a_{i-1} … a_{i 1} … a_{m-1} … a_m)
=ai⋅(∑mj=1aj−ai)=a_i·(\sum_{j=1}^m a_j-a_i)
=ai⋅∑mj=1aj−a2i=a_i·\sum_{j=1}^m a_j-a_i^2
於是乎Sum=∑mi=1sumi=∑mi=1ai⋅∑mj=1aj−∑mi=1a2iSum=\sum_{i=1}^m sum_i=\sum_{i=1}^m a_i·\sum_{j=1}^m a_j-\sum_{i=1}^m a_i^2
所以這個值即為這個點集中的所有數和的平方減去這個點集中所有數的平方和
於是新鮮的程式碼就出爐了,
然而發現眾大神們沒有一個的寫法和我一樣0.0

#include<bits/stdc  .h>
using namespace std;
#define M 200005
#define P 10007
int A[M],B[M];
void Rd(int &res){
char c;res=0;
while(c=getchar(),!isdigit(c));
do res=(res<<3) (res<<1) (c^48);
while(c=getchar(),isdigit(c));
}
vector<int>edge[M];
int val[M];
int ans1,ans2;
void dfs(int x,int pre){
int tmp=0,sum=0,mx1=0,mx2=0;//mx1表示最大數,mx2表示最小數【與點x距離為1的點】
for(int i=0;i<edge[x].size();i  ){
int y=edge[x][i];
if(val[y]>mx1){
mx2=mx1;
mx1=val[y];
}else if(val[y]>mx2){
mx2=val[y];
}tmp=(tmp val[y])%P;//求和
sum=(1ll*sum val[y]*val[y])%P;//求平方和
if(y==pre)continue;
dfs(y,x);
}ans1=max(ans1,mx1*mx2);
ans2=(1ll*ans2 tmp*tmp-sum)%P;//值為和的平方減去平方和
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<n;i  ){
int a,b;
Rd(a);Rd(b);
edge[a].push_back(b);
edge[b].push_back(a);
}for(int i=1;i<=n;i  )Rd(val[i]);
dfs(1,0);
printf("%d %d\n",ans1,(ans2 P)%P);
return 0;
}

C題:
這題明顯是dp題
但是博主並沒有想到。。。
然而這無傷大雅
博主的最短路【DijkstraDijkstra】程式碼仍舊WaterWater了70分,最後情況太多MLE了。。。
敲完DijkstraDijkstra的時候博主自信的認為不會MLE,這是個AC程式碼
【然而事實上是隻考慮了時間複雜度,直接忘記了還有空間這種東東】
附上DijkstraDijkstra70分程式碼:

//PS:最短路70分程式碼。。。
#include<bits/stdc  .h>
using namespace std;
#define M 10005
#define N 1005
int x[M],y[M],l[M],r[M];
int n,m,k;
bool mark[M][N];
struct node{
int c,x,h,cnt;
bool operator <(const node &A)const{
return c>A.c;
}
};
priority_queue<node>Q;
int ans;
void Dijkstra(){//沒事麼好分析的,Dijkstra肯定會吧。。
node tmp;
tmp.c=0;
tmp.x=0;
tmp.cnt=0;
for(int i=1;i<=m;i  ){
tmp.h=i;
Q.push(tmp);
}while(!Q.empty()){
tmp=Q.top();Q.pop();
if(mark[tmp.x][tmp.h])continue;
mark[tmp.x][tmp.h]=1;
if(tmp.cnt>ans)ans=tmp.cnt;//可以飛過的管道數 
if(tmp.x==n){
printf("1\n%d\n",tmp.c);
exit(0);
}node nxt;
nxt.x=tmp.x 1;
nxt.h=tmp.h-y[tmp.x];
if(nxt.h>0){
if(!l[nxt.x]&&!r[nxt.x]){
nxt.c=tmp.c;nxt.cnt=tmp.cnt;
if(!mark[nxt.x][nxt.h])Q.push(nxt);
}else if(nxt.h>l[nxt.x]&&nxt.h<r[nxt.x]){
nxt.c=tmp.c;nxt.cnt=tmp.cnt 1;
if(!mark[nxt.x][nxt.h])Q.push(nxt);
}
}for(int i=1;;i  ){
nxt.h=tmp.h i*x[tmp.x];
if(nxt.h>m)nxt.h=m;
if(!l[nxt.x]&&!r[nxt.x]){
nxt.c=tmp.c i;nxt.cnt=tmp.cnt;
if(!mark[nxt.x][nxt.h])Q.push(nxt);
}else if(nxt.h>l[nxt.x]&&nxt.h<r[nxt.x]){
nxt.c=tmp.c i;nxt.cnt=tmp.cnt 1;
if(!mark[nxt.x][nxt.h])Q.push(nxt);
}if(nxt.h==m)break;
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<n;i  )scanf("%d %d",&x[i],&y[i]);
for(int i=1;i<=k;i  ){
int p,L,R;
scanf("%d %d %d",&p,&L,&R);
l[p]=L;r[p]=R;
}Dijkstra();
printf("0\n%d\n",ans);
return 0;
}

而後這題DijkstraDijkstra是不可能敲到AC
所以還是老老實實的敲dp吧。。。
每一對id,high{id,high}的值都可以從id−1,high−k⋅xi{id-1,high-k·x_i}或id−1,high yiid-1,high y_i轉移過來
於是很容易寫出dp程式碼,複雜度為O(n⋅m2n·m^2)
會TLE。。。
然而我們再仔細觀察一下會發現【這是個完全揹包問題。。。所以採用完全揹包的優化方法就行了】
其實如果我們保證在idid這個位置小於highhigh的高度上的dp值已經最優,
其實id,highid,high的dp值只會從id,high−xiid,high-x_i或id−1,high−xiid-1,high-x_i或id−1,high yiid-1,high y_i轉移過來
但是要注意的在id,high−xiid,high-x_i這個位置小鳥是可以碰到管道的【否則75分】
(這只是一個dp轉移的中介,最終當idid位置上的dp值全部計算完畢的時候需要將碰到管道的情況清空)
時間複雜度為O(n⋅mn·m),空間複雜度為O(n⋅mn·m)
然而這一題某一橫座標idid上的dp值顯然只會從id−1id-1上轉移過來
所以我們可以用滾動陣列優化空間,將空間複雜度降為O(n mn m)
於是程式碼出爐:

#include<bits/stdc  .h>
using namespace std;
#define M 10005
#define N 1005
#define oo 2000000000
int x[M],y[M],l[M],r[M];
//x[id]表示在橫座標為id的點上點選一次螢幕能升高的距離
//y[id]表示在橫座標為id的點上不點選螢幕會下降的距離
//l[id]表示在橫座標為id的點上管道的下表面
//r[id]表示在橫座標為id的點上管道的上表面
//PS:若該處沒有管道,下表面為0,上表面為m 1
int n,m,k;
int dp[2][N];
void Rd(int &res){
char c;res=0;
while(c=getchar(),!isdigit(c));
do res=(res<<3) (res<<1) (c^48);
while(c=getchar(),isdigit(c));
}
int main() {
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<n;  i)Rd(x[i]),Rd(y[i]);
for(int i=0;i<=n;  i)l[i]=0,r[i]=m 1;
for(int i=1;i<=k;  i){
int p,L,R;
Rd(p);Rd(L);Rd(R);
l[p]=L;
r[p]=R;
}for(int j=1;j<=m;  j)dp[1][j]=oo,dp[0][j]=0;
int cur=0,cnt=0;
for(int i=0;i<n;  i){
cur=!cur;
for(int j=1;j<=m;  j){//dp轉移
if(j-y[i]>l[i 1]&&j-y[i]<r[i 1]&&dp[cur][j-y[i]]>dp[!cur][j])dp[cur][j-y[i]]=dp[!cur][j];
int H=j x[i];
if(H>m)H=m;
int len=dp[!cur][j];
if(dp[cur][j]<len)len=dp[cur][j];
len;
if(dp[cur][H]>len)dp[cur][H]=len;
}bool f=0;
for(int j=1;j<=m;  j){
if(j<=l[i 1]||j>=r[i 1])dp[cur][j]=oo;
else if(dp[cur][j]!=oo&&r[i 1]!=m 1&&!f)f=1,cnt  ;//飛過的管道數
dp[!cur][j]=oo;
}
}int ans=oo;
for(int i=1;i<=m;  i)ans=min(ans,dp[cur][i]);
if(ans!=oo)printf("1\n%d\n",ans);
else printf("0\n%d\n",cnt);
return 0;
}

270。。。。。