NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃
 最新文章
頁: [1] 2 3 ... 10
 1 
 於: 六月 09, 2018, 01:50:16 pm 
作者 Felicity - 最新文章 由 Felicity
這大概是送分題了

 2 
 於: 四月 04, 2018, 01:36:18 am 
作者 liouzhou_101 - 最新文章 由 xavier13540
構造一張圖 G = (V, E),其中
  • V 裡的任一元素代表兩人的所在位置,以無序對 (i, j) (若 hi = hj),或有序對 (i, j+1/2) (若 min{hj, hj+1} < hi < max{hj, hj+1}) 表示。
  • 設 u, v ∈ V。規定 uv ∈ E 若且唯若兩人可以在只上山或下山一次的情況下從 u 到達 v。
不難發現題目要問的就是從 (0, n+1) 到任意 (i, i) 的最短路徑長度減 1,可用一次 BFS 解決。因為 |V| = O(n2),且每個頂點的度數 (degree) 都不超過 4,可知整體的時間複雜度是 O(n2)。
值得一提的是,一定存在一條從 (0, n+1) 到某個 (i, i) 的路徑。我們把 G 裡的頂點分成下面這幾種,並討論它們的度數。
  • (0, 0), (0, n+1), (n+1, n+1) 的度數都是 1。
  • 若 i ≠ 0, n+1 且 hi = 0,則 (0, i) 和 (i, n+1) 的度數都是 2。
  • 若 i ≠ 0, n+1,則 (i, i) 的度數是 3。
  • 若 i ≠ j 且 hi = hj,則 (i, j) 的度數是 4 (若 i, j 同為山頂或山谷) 或 0 (若 i, j 一者是山頂另一者是山谷)。
  • 設 v := (i, j+1/2) 為一合法頂點,則 v 的度數是 2。
令 H 為 G 中包含頂點 (0, n+1) 的連通部分 (connected component)。因為 H 的頂點度數和為偶數,可知 H 必定包含某個 (i, i),亦即存在從 (0, n+1) 到某個 (i, i) 的路徑。

以下是我的 C++ code:
代碼: [選擇]
#include<cassert>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define N 210
typedef pair<int, int> pii;
int n, h[2*N];
vector<int> g[4*N*N];
bool vis[4*N*N];
int state(int i, int j){
    if(i > j){
        swap(i, j);
    }
    return i*(2*n+3)+j;
}
int move(int i, int j, int di, int dj){
    int c = (i&2)-1;
    if(j&1){
        if(c*h[i+2*di] < c*h[j+dj]){
            return state(i+di, j+dj);
        }else if(c*h[i+2*di] == c*h[j+dj]){
            return state(i+2*di, j+dj);
        }else{
            return state(i+2*di, j);
        }
    }else{
        if(c*h[i+2*di] < c*h[j+2*dj]){
            return state(i+di, j+2*dj);
        }else if(c*h[i+2*di] == c*h[j+2*dj]){
            return state(i+2*di, j+2*dj);
        }else{
            return state(i+2*di, j+dj);
        }
    }
}
bool meet(int v){
    return v/(2*n+3) == v%(2*n+3);
}

int main(){
    while(scanf("%d", &n), n){
        h[0] = h[2*n+2] = 0;
        for(int i=1; i<=n; i++){
            scanf("%*d%d", h+2*i);
        }
        scanf("%*d");
        for(int i=0; i<(2*n+3)*(2*n+3); i++){
            g[i].clear();
        }
        g[state(0, 0)].push_back(move(0, 0, 1, 1));
        g[state(0, 2*n+2)].push_back(move(0, 2*n+2, 1, -1));
        g[state(2*n+2, 2*n+2)].push_back(move(2*n+2, 2*n+2, -1, -1));
        for(int j=4; j<=2*n-2; j+=4) if(h[j] == 0){
            g[state(0, j)].push_back(move(0, j, 1, -1));
            g[state(0, j)].push_back(move(0, j, 1, 1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, -1, -1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, 1, -1));
        }
        for(int i=2, c=1; i<=2*n; i+=2, c*=(-1)){
            for(int j=i; j<=2*n; j+=4) if(h[i] == h[j]){
                g[state(i, j)].push_back(move(i, j, -1, -1));
                g[state(i, j)].push_back(move(i, j, -1, 1));
                g[state(i, j)].push_back(move(i, j, 1, -1));
                g[state(i, j)].push_back(move(i, j, 1, 1));
            }
            for(int j=1; j<=2*n-1; j+=4) if(h[j-1]<h[i] && h[i]<h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, -c));
                g[state(i, j)].push_back(move(i, j, 1, -c));
            }
            for(int j=3; j<=2*n+1; j+=4) if(h[j-1]>h[i] && h[i]>h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, c));
                g[state(i, j)].push_back(move(i, j, 1, c));
            }
        }
        bool sol = false;
        memset(vis, false, sizeof(vis));
        queue<pii> bfs;
        bfs.push(make_pair(0, state(0, 2*n+2)));
        vis[state(0, 2*n+2)] = true;
        while(!bfs.empty()){
            pii p = bfs.front(); bfs.pop();
            int d=p.first, v=p.second;
            if(meet(v)){
                printf("%d\n", d-1);
                sol=true; break;
            }
            for(int i=0; i<(int)g[v].size(); i++) if(!vis[g[v][i]]){
                bfs.push(make_pair(d+1, g[v][i]));
                vis[g[v][i]] = true;
            }
        }
        assert(sol);
    }
    return 0;
}


 3 
 於: 三月 19, 2018, 02:33:49 pm 
作者 oToToT - 最新文章 由 oToToT
DP即可
代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 1000000 + 5;
const lld INF = 1LL<<60;
lld arr[N], sum[N], dp[N];

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
lld cnt=0, mm = -INF;
for(int i=1;i<=n;i++){
cnt += arr[i];
mm = max(cnt,mm);
if(cnt < 0) cnt = 0;
sum[i] = mm;
}
dp[0]=-INF; dp[1]=-INF; dp[2]=-INF;
lld mx = -INF;
for(int i=3;i<=n;i++){
dp[i] = max(mx+arr[i], sum[i-2]+arr[i]);
mx = max(mx, dp[i]);
}
lld ans = -INF;
for(int i=1;i<=n;i++) ans=max(ans, dp[i]);
cout<<ans<<'\n';
return 0;
}

 4 
 於: 三月 19, 2018, 02:32:42 pm 
作者 oToToT - 最新文章 由 oToToT
看是不是一個團就好
代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 100000 + 5;

set<int> G[N];

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=0;i<m;i++){
int u, v; cin>>u>>v;
if(u==v) continue;
G[u].insert(v);
G[v].insert(u);
}
bool flag = false;
for(int i=1;i<=n;i++){
if(G[i].size() < n-1) flag = true;
}
cout<<(flag?n:0)<<'\n';
return 0;
}

 5 
 於: 三月 19, 2018, 02:31:22 pm 
作者 oToToT - 最新文章 由 oToToT
Hash一下
代碼: [選擇]
#include <cstdio>
#include <cstdlib>
typedef long long lld;
const int N = 500000 + 1;
const lld q1 = 2147483587;
const lld p1 = 1208220623;
const lld q2 = 2147483647;
const lld p2 = 1000000007;

int main(){
int t; scanf("%d", &t);
while(t--){
int n, m; scanf("%d%d", &n, &m);
if(n == 1){
int ww;
for(int i=0;i<m;i++) scanf("%d", &ww);
puts("Yes"); continue;
}
if(m == 1){
int ww;
for(int i=0;i<n;i++) scanf("%d", &ww);
puts("Yes"); continue;
}
lld he1 = 1, me1 = 1, he2=1, me2=1;
bool ans = 1;
for(int i=0;i<m;i++){
int x;
scanf("%d", &x);
if(i==m-1) continue;
he1 = (he1 * p1 % q1 + x) % q1;
he2 = (he2 * p2 % q2 + x) % q2;
}
for(int i=1;i<n;i++){
lld meme1 = 1, meme2 = 1;
me1 = 1, me2 = 1;
for(int j=0;j<m;j++){
int x;
scanf("%d", &x);
if(j!=0){
meme1 = (meme1 * p1 % q1 + x) % q1;
meme2 = (meme2 * p2 % q2 + x) % q2;
}
if(j!=m-1){
me1 = (me1 * p1 % q1 + x) % q1;
me2 = (me2 * p2 % q2 + x) % q2;
}
}
ans &= ((meme1==he1) and (meme2==he2));
he1 = me1;
he2 = me2;
}
puts(ans?"Yes":"No");
}
return 0;
}

 6 
 於: 三月 19, 2018, 02:30:02 pm 
作者 oToToT - 最新文章 由 oToToT
代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

const int vn=2000+3;

vector <int> edges[vn];

const lld mod=1e9+7;

#define pr pair<lld,lld>
#define F first
#define S second

lld fp(lld n,lld a){
lld re=1;
for(;a;a/=2){
if(a&1){
re*=n;
re%=mod;
}
n*=n;
n%=mod;
}
return re;
}

lld func(lld n){return fp(n,mod-2);}

lld up[vn],dn[vn];

void init(){
up[1]=1;
dn[1]=1;
for(int i=2;i<vn;i++){
up[i]=up[i-1]*i%mod;
dn[i]=dn[i-1]*func(i)%mod;
}
}

lld C(lld n,lld m){
return ((up[n]*dn[m]%mod)*dn[n-m])%mod;
}

pr dfs(int p,int nw){
lld ans=1;
vector<pr> v;
for(auto au:edges[nw]){
if(au==p) continue;
v.push_back(dfs(nw,au));
}
lld sum=0;
for(auto au:v){sum+=au.S;}
lld ssum=sum;
for(auto au:v){
ans*=au.F;
ans%=mod;
}
for(int i=0;i<(int)v.size()-1;i++){
ans*=C(sum,v[i].S);
ans%=mod;
sum-=v[i].S;
}
return {ans,ssum+1};
}

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N;
cin>>N;
init();
int a,b;
while(cin>>a>>b){
a--;
b--;
edges[a].push_back(b);
edges[b].push_back(a);
}
lld ans=0;
for(int i=0;i<N;i++){
ans+=dfs(i,i).F;
ans%=mod;
}
cout<<ans<<endl;
return 0;
}

 7 
 於: 三月 19, 2018, 02:27:55 pm 
作者 oToToT - 最新文章 由 oToToT
觀察規律或暴搜即可
代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int k, n; cin>>k>>n;
if(k==0){
for(int i=0;i<n;i++) cout<<i<<'\n';
}else if(k==1){
int cnt = 0;
for(llu i=1;i<10;i++){
for(llu j=0;j<100;j++){
if(j==i*10) j+=10;
cout<<i<<j<<i+j<<'\n';
cnt++;
if(cnt == n) return 0;
}
}
assert(0);
}else if(k==2){
llu cur = 10;
for(llu i=1;i<=n;i++){
if(i==cur) cur*=10;
cout<<i<<i<<i<<cur*i+i+i<<'\n';
}
}
return 0;
}

 8 
 於: 十二月 03, 2017, 07:33:02 pm 
作者 Felicity - 最新文章 由 Felicity
#include<stdlib.h>
#include<stdio.h>
int main()
{
   int i,n,a,b,c,j=0,k,flag;
   char d,s[5];
   scanf("%d",&n);
   char ans2[n];
   int ans1[n][2];
   for(i=0;i<n;i++)
   {
      flag=0;
      scanf("%d %d %d %c %s",&a,&b,&c,&d,&s);
      for(k=0;k<j;k++)
      {
         if(b==ans1[k][0]&&d==ans2[k])
            flag=1;
      }
      if(s[0]=='A'&&s[1]=='C'&&c<180&&flag==0)
      {
         j++;
         ans2[j-1]=d;
         ans1[j-1][0]=b;
         ans1[j-1][1]=c;
      }
   }
   
   for(i=0;i<j;i++)
   {
      printf("Send balloon of %c to team %d at time %d.\n",ans2,ans1[0],ans1[1]);
   }
   printf("Go get snacks.\n");
   return 0;
}

 9 
 於: 十二月 03, 2017, 07:32:30 pm 
作者 Felicity - 最新文章 由 Felicity
#include<stdlib.h>
#include<stdio.h>
int main()
{
   long long n,k,a;
   scanf("%lld %lld",&n,&k);
   a=n-k-k;
   if(a<0)
      a*=-1;
   printf("%lld\n",a);
   return 0;
}

 10 
 於: 十二月 03, 2017, 07:31:44 pm 
作者 Felicity - 最新文章 由 Felicity
#include<stdlib.h>
#include<stdio.h>
int main()
{
   int t,x,y,a,b;
   scanf("%d %d %d",&t,&x,&y);
   t-=y;
   a=y;
   b=t/x;
   a+=t-y*b;
   if(t%x>(x-y))
      a-=t%x-(x-y);
   printf("%d %d\n",a,b);
   return 0;
}

頁: [1] 2 3 ... 10