結果：過了250，challenge環節-1。 最後rate -9。 第一次TC連續跌兩次了，只能呵呵了 主要還是250把題目看錯一次，然後某SIR來個電話有事。。。 然後賽後好久才知道把450看錯，我以為是能到達每一個點。。 不過結束之後很快把DIV2的做了。。。。 DIV2 A：直接和前一個比較 DIV2 B：貪心，將剩下的數排序之後。先取一個最大的，然後找到一個盡可能小的數，剛好和之前選的數相加能超過自己的得分。剩下一個數選盡可能小的。 DIV2C：大致寫得很隨意 。枚舉坐標區間大致是[-50,100]，然後就是150*150枚舉目標坐標。 遍歷所有點，每個點到目標點的步數是知道的，大概就是坐標差。然後判斷是否可達一下。 剩下的步數，當然是n左n右，m上m下的結構。然後統計一下每個方向有多少步，組合數搞一下就行了。 要是這次做的是div2那應該爽了。。。 [cpp] class WolfPackDivTwo { public: LL c[55][55]; void Init(){ for(int i=0;i<=50;i++){ c[i][0]=c[i][i]=1; for(int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; } } LL check(vi x,vi y,int cx,int cy,int m){ LL ans=1; for(int i=0;i<x.size();i++){ int a=abs(x[i]-cx)+abs(y[i]-cy); if(a>m || (m-a)&1) return 0; int up=0,down=0,left=0,right=0; int k=m-a; if(x[i]>cx) left=x[i]-cx; else right=cx-x[i]; if(y[i]>cy) up=y[i]-cy; else up=cy-y[i]; LL t=0; for(int j=0;j*2<=k;j++){ int l=left+j; int r=right+j; int u=up+(k-2*j)/2; int d=down+(k-2*j)/2; t=((((c[m][l]*c[m-l][r])%MOD)*c[m-l-r][u]%MOD)+t)%MOD; } ans=((LL)ans*t)%MOD; } return ans; } int calc(vector <int> x, vector <int> y, int m) { LL ans=0; Init(); for(int i=-51;i<=151;i++){ for(int j=-51;j<=151;j++){ ans=(ans+check(x,y,i,j,m))%MOD; } } return ans; } } class WolfPackDivTwo { public: LL c[55][55]; void Init(){ for(int i=0;i<=50;i++){ c[i][0]=c[i][i]=1; for(int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; } } LL check(vi x,vi y,int cx,int cy,int m){ LL ans=1; for(int i=0;i<x.size();i++){ int a=abs(x[i]-cx)+abs(y[i]-cy); if(a>m || (m-a)&1) return 0; int up=0,down=0,left=0,right=0; int k=m-a; if(x[i]>cx) left=x[i]-cx; else right=cx-x[i]; if(y[i]>cy) up=y[i]-cy; else up=cy-y[i]; LL t=0; for(int j=0;j*2<=k;j++){ int l=left+j; int r=right+j; int u=up+(k-2*j)/2; int d=down+(k-2*j)/2; t=((((c[m][l]*c[m-l][r])%MOD)*c[m-l-r][u]%MOD)+t)%MOD; } ans=((LL)ans*t)%MOD; } return ans; } int calc(vector <int> x, vector <int> y, int m) { LL ans=0; Init(); for(int i=-51;i<=151;i++){ for(int j=-51;j<=151;j++){ ans=(ans+check(x,y,i,j,m))%MOD; } } return ans; } } DIV1 A：大概和DIV2的B是差不多的。 也是貪心，先排序之後，找一個最大的。然後再找一個盡可能小的，和之前選的相加超過自己的得分的。 最後一個是在二者之前去找，如果沒有說明已經找不到這樣的組合了。 DIV1 B：題目看錯了，囧。。。。 我以為是從0出發，能到達剩下N-1個點，只能呵呵了。 是說怎麼大家都是用從0到N-1的最短路去做。。。 將高度離散化一下，dp[i][j]表示在i這個點，高度為w[j]時的最優解。 放到spfa裡面去不斷更新就行了。TAT [cpp] class SkiResorts { public: long long minCost(vector <string> r, vector <int> h) { int n=h.size(); int w[n]; LL dp[n][n]; for(int i=0;i<n;i++) w[i]=h[i]; sort(w,w+n); bool in[n];mem(in,false); mem(dp,-1); for(int i=0;i<n;i++) dp[0][i]=abs(h[0]-w[i]); queue<int>que; que.push(0); in[0]=true; while(!que.empty()){ int u=que.front(); que.pop(); in[u]=false; for(int i=0;i<n;i++){ if(r[u][i]=='N') continue; for(int j=0;j<n;j++){ for(int k=0;k<=j;k++){ if(dp[i][k]==-1||dp[i][k]>dp[u][j]+abs(h[i]-w[k])){ dp[i][k]=dp[u][j]+abs(h[i]-w[k]); if(in[i]==false){ in[i]=true; que.push(i); } } } } } } LL ans=-1; for(int i=0;i<n;i++) if(dp[n-1][i]!=-1){ if(ans==-1||dp[n-1][i]<ans) ans=dp[n-1][i]; } return ans; } } class SkiResorts { public: long long minCost(vector <string> r, vector <int> h) { int n=h.size(); int w[n]; LL dp[n][n]; for(int i=0;i<n;i++) w[i]=h[i]; sort(w,w+n); bool in[n];mem(in,false); mem(dp,-1); for(int i=0;i<n;i++) dp[0][i]=abs(h[0]-w[i]); queue<int>que; que.push(0); in[0]=true; while(!que.empty()){ int u=que.front(); que.pop(); in[u]=false; for(int i=0;i<n;i++){ if(r[u][i]=='N') continue; for(int j=0;j<n;j++){ for(int k=0;k<=j;k++){ if(dp[i][k]==-1||dp[i][k]>dp[u][j]+abs(h[i]-w[k])){ dp[i][k]=dp[u][j]+abs(h[i]-w[k]); if(in[i]==false){ in[i]=true; que.push(i); } } } } } } LL ans=-1; for(int i=0;i<n;i++) if(dp[n-1][i]!=-1){www.2cto.com if(ans==-1||dp[n-1][i]<ans) ans=dp[n-1][i]; } return ans; } }
