首页 > 代码库 > NOIP2010 题解

NOIP2010 题解

2024-07-13 09:37:08   221人阅读

机器翻译

　　题解：模拟

 1 #include <cstdio> 2 #include <cstring> 3  4 const int MAXN = 1000; 5  6 int n, m, cj, now, MinV, MinId, Pri, a[MAXN+10], in[MAXN+10]; 7  8 int main(){ 9     memset(in, -1, sizeof(in));10     scanf("%d %d", &n, &m), now = Pri = 0;11     for (int i=0; i<m; i++){12         scanf("%d", &cj);13         if (~in[cj]) continue;14         Pri ++;15         if (now+1<=n) now ++, in[cj] = i;16         else {17             MinV = 0x3f3f3f3f;18             for (int j=0; j<=MAXN; j++)19                 if (in[j]<MinV && in[j]!=-1) MinV = in[j], MinId = j;20             in[MinId] = -1, in[cj] = i; 21         } 22     }23     printf("%d\n", Pri);24 }
translate.cpp

 

乌龟棋

　　题解：dp

 1 #include <cstdio> 2 #include <cstring> 3  4 const int MAXN = 350+2; 5 const int MAXE = 40+2; 6  7 int n, m, cj, a[MAXN], b[6], dp[MAXE][MAXE][MAXE][MAXE]; 8  9 int main(){10     memset(dp, 0, sizeof(dp));11     12     scanf("%d %d", &n, &m);13     for (register int i=0; i<n; i++)14         scanf("%d", &a[i]);15     for (register int i=0; i<m; i++)16         scanf("%d", &cj), b[cj] ++;17 18     dp[0][0][0][0] = a[0];19     for (register int A=0; A<=b[1]; A++)20         for (register int B=0; B<=b[2]; B++)21             for (register int C=0; C<=b[3]; C++)22                 for (register int D=0; D<=b[4]; D++){23                     cj = A+B+B+C+C+C+D+D+D+D;24                     if (A && dp[A-1][B][C][D]+a[cj]>dp[A][B][C][D])    dp[A][B][C][D] = dp[A-1][B][C][D]+a[cj];25                     if (B && dp[A][B-1][C][D]+a[cj]>dp[A][B][C][D]) dp[A][B][C][D] = dp[A][B-1][C][D]+a[cj];26                     if (C && dp[A][B][C-1][D]+a[cj]>dp[A][B][C][D]) dp[A][B][C][D] = dp[A][B][C-1][D]+a[cj];27                     if (D && dp[A][B][C][D-1]+a[cj]>dp[A][B][C][D]) dp[A][B][C][D] = dp[A][B][C][D-1]+a[cj];28                 }29     printf("%d\n", dp[b[1]][b[2]][b[3]][b[4]]);30 }
tortoise.cpp

 

关押罪犯

　　题解：并查集。既然只有两个监狱，那么如果a和b没有在一个监狱，b和c没有在一个监狱，那么a和c一定在一个监狱

　　把怒气值从大到小拍个序，依次处理

　　并查集[1, n]表示和自己一起的，[n+1, 2n]表示不和自己一起的

 1 #include <cstdio> 2 #include <algorithm> 3 using std::sort; 4  5 const int MAXN = 20000+10; 6 const int MAXM = 100000+10; 7  8 int n, m, f[MAXN*2]; 9 10 struct Relation{11     int a, b, c;12 13     friend bool operator < (const Relation& A, const Relation& B){14         return A.c>B.c;15     } 16 }r[MAXM];17 18 inline int Find(int x){19     return f[x]==x ? x : f[x] = Find(f[x]);20 }21 22 inline int Solve(){23     sort(r, r+m);24     int a, b;25     for (int i=0; i<m; i++){26         a = Find(r[i].a), b = Find(r[i].b);27         if (a==b) return r[i].c;28         else f[a] = Find(r[i].b+n), f[b] = Find(r[i].a+n);29     }30     return 0;31 }32 33 int main(){34     scanf("%d %d", &n, &m);35     for (int i=1; i<=2*n; i++)36         f[i] = i;37     for (int i=0; i<m; i++)38         scanf("%d %d %d", &r[i].a, &r[i].b, &r[i].c);39 40     printf("%d\n", Solve());41 }
prison.cpp


联系
我们