NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃
 最新文章
頁: [1] 2 3 ... 10
 1 
 於: 十月 17, 2018, 02:39:55 pm 
作者 sagit - 最新文章 由 sagit
這題要以二進位來思考,
假設 A=100100010,
則滿足 A+B=A|B 條件的 B,
在 A 中為 1 的位元必定為 0,
也就是 B=0xx0xxx0x,
其中的 x 可為 0 或 1,
因此只要數一下 A 裡面有幾個位元是 0,
算出 2 的次方就可以得到答案。

但是題目又規定 B <=X ,
所以我們要將 X 分段處理,
假設 X=1001000100,
先找出最左邊第一個出現的 1 為 1000000000,
分出第一段數字 xxxxxxxxx,(不含上面的數)
也就是 0 ~ 111111111 (1000000000-1),
再用這一段去找有幾個位元在 A 中是 0。
接下來再找出第二個出現的 1 為 1000000,
而第二段數字為 1000xxxxxx,
也就是 1000000000 ~ 1000111111 (1001000000-1),
數字的最前面固定是 1000,
一樣找出後面的位元有幾個在 A 中是 0。
要注意的是,如果這個位元在 X 和在 A 中同時為 1,
則後面就不會再有答案,必須中斷。

再來,因為這個做法只能處理到 X-1,
所以 X 要另外處理。
最後,因為題目要求要正整數,
但這個做法會包含 0,
所以答案要再減一。

核心程式碼:
代碼: [選擇]
for (bit=(1<<30), ans=0; bit; bit>>=1)
{
    if ((bit&x)==0) continue;
    for (bit2=(bit>>1), c=0; bit2; bit2>>=1)
        if ((bit2&a)==0) c++;
    ans+=A[c];
    if (bit&a) break;
}
if ((a|x)==(a+x)) ans++;
printf("%d\n", ans-1);
PS. A[ i ] 為 2i, 可在程式一開始先算出它們的值。

 2 
 於: 十月 15, 2018, 02:56:08 pm 
作者 sagit - 最新文章 由 sagit
這題答案的長方形,如果不是 1x2,就一定是 1x3 的大小,
以這個方式每個都找一找就可以找到答案。

 3 
 於: 十月 15, 2018, 02:49:58 pm 
作者 sagit - 最新文章 由 sagit
將下限L設為 1,上限U設為 4e18 (即 4*1018),
< 和 <= 時修正U (k比U小的時候才修正),
而 > 和 >= 時修正L (k比L大的時候才修正),
U-L+1即是答案,
要注意如果答案是負的則輸出0,
而答案大於 1e18 則是 INF。

 4 
 於: 十月 15, 2018, 02:43:36 pm 
作者 sagit - 最新文章 由 sagit
假設字串長度為L,
以兩層的for迴圈,
第一層 i=1~L/2,第二層 j=i+1~L*2/3,
則可以分解成三個子字串:0~i-1、i~j-1、j~L-1,
任一子字串的長度為2以上,且第一個字元為0時不合法,
接下來再將三個子字串各自轉成long long int,
再判斷a+b==c是否成立即可。

 5 
 於: 十月 15, 2018, 02:18:21 pm 
作者 oToToT - 最新文章 由 sagit
用三個陣列來記錄,A[ i ]記錄輸入的數字是多少,
B[ i ]記錄從第一個數到第i個數取某些數字(至少取一個)的最大值是多少,(第i個不一定要取),
B[1]=A[1],i=2~N-2時,B[ i ]=max(A[ i ], B[ i-1 ], A[ i ]+B[ i-1 ]),
而 C[ i ]記錄以第i個為最後一個的最大不連續和是多少,(第i個一定要取)
C[3]=A[1]+A[3],i=4~N時,C[ i ]=max(C[ i-1 ], B[ i-2 ])+A[ i ],
即可求出答案。

 6 
 於: 十月 08, 2018, 04:24:59 pm 
作者 oToToT - 最新文章 由 sagit
其實只要檢查 m!=n*(n-1)*2 即可,後面的資料完全不需要輸入。
另外,因為 n 最大為 10^5,
n*(n-1) 會超過 int 的範圍,要注意,
而因為 m 最大也是 10^5,
所以可以 反推回去 n 超過 500 的情況一定是 n,
就不用再乘了。
也就是:
代碼: [選擇]
if (n>=500||m!=n*(n-1)*2) cout << n << endl;
else cout << 0 << endl;

 7 
 於: 六月 09, 2018, 01:50:16 pm 
作者 Felicity - 最新文章 由 Felicity
這大概是送分題了

 8 
 於: 四月 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;
}


 9 
 於: 三月 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;
}

 10 
 於: 三月 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;
}

頁: [1] 2 3 ... 10