NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組初賽
 ProblemC-混色模式(補code)

作者 主題: ProblemC-混色模式(補code)  (閱讀 1887 次)

darry140

  • 初級會員
  • **
  • 文章數: 24
    • 檢視個人資料
ProblemC-混色模式(補code)
« 於: 十二月 08, 2013, 08:45:28 am »

Prefix sum
注意重複算到解的問題
(其實這樣只過範測,但是80000 80000那筆對了應該就對了吧)
----------------
NPSC2013官網公布測資了
官測AC。
----------------
代碼: [選擇]
#include <iostream>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
long long A[80010],S[80010],ans;
long long DP(int N,int M)//N<=M
{
for(int i=1;i<N;i++)
A[i]=min(N-i,i)*2-(i<=N-i?1:0);
S[1]=A[1];
for(int i=2;i<N;i++)
S[i]=S[i-1]+A[i];
ans=0;
for(int i=1;i<N;i++)
ans+=A[i]*S[min(M-i,N-1)];
return ans;
}
int main()
{
int T;
cin>>T;
int N,M;
while(T--)
{
cin>>N>>M;
cout<<DP(min(N,M),max(N,M))<<endl;
}
return 0;
}
« 上次編輯: 十二月 13, 2013, 11:58:23 pm 由 darry140 »
記錄

WYJOIER

  • 新手
  • *
  • 文章數: 7
    • 檢視個人資料
Re: ProblemC-混色模式(補code)
« 回覆 #1 於: 四月 23, 2014, 05:23:24 pm »

附上我的解法:
代碼: [選擇]
#include <cstdio>
#include <algorithm>
#define MaxNM 80010
using namespace std;
int main()
{
    int T , N , M;
    unsigned long long int dp[MaxNM] , Answer;
    scanf("%d",&T);
    while( T-- )
    {
           scanf("%d%d",&N,&M);
           if(N > M)swap(N,M);
           dp[0] = 0LL;
           for( int i = 1; i <= N-1; i++ )dp[i] = ( (N-i) >= i ? 2*i-1 : (N-i)*2 ) + dp[i-1];
           Answer = 0LL;
           for( int i = 1; i <= N-1; i++ )Answer += (dp[i]-dp[i-1])*dp[min(M-i,N-1)];
           printf("%llu\n",Answer);
    }
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組初賽
 ProblemC-混色模式(補code)