NEERC 2014, Eastern subregional contest

最近做的一场比赛，把自己负责过的题目记一下好了。

Problem B URAL 2013 Neither shaken nor stirred

题意：一个有向图，每个结点一个非负值，可以转移到其他结点。初始时刻从结点出发，然后每次到达一个结点询问上一个到达的正值结点的权值，离开结点时也要询问一下，因为当前结点可能为正数，答案就是这个值了，如果不存在这个样的正权值输出“sober",或者不明确时输出“unkonwn”。

分析：可以当做树形dp来做。dp[u][0]表示进入结点时上一个正权值，dp[u][1]表示离开结点时的正权值, val[u]表示结点u权值,inf表示不明确情况。

转移这样来做：

对于边u->v，首先考虑dp[v][1]， val[v] != 0时， dp[v][1] = val[v]，否则dp[v][1] = dp[v][0]。

如果v没有访问过,dp[v][0] = dp[u][1]， v访问过，那么dp[v][0] != dp[u][1]时，更新dp[v][0] = inf，并且当val[v] = 0时，要从v点重新出发dfs，因为此时dp[v][1]值也会变化。

代码：

 #include <bits/stdc++.h>

 #define pb push_back

 #define mp make_pair

 #define esp 1e-8

 #define lowbit(x) ((x)&(-x))

 #define lson   l, m, rt<<1

 #define rson   m+1, r, rt<<1|1

 #define sz(x) ((int)((x).size()))

 #define pb push_back

 #define in freopen("solve_in.txt", "r", stdin);

 #define out freopen("solve_out.txt", "w", stdout);

 #define bug(x) printf("Line : %u >>>>>>\n", (x));

 #define inf 0x0f0f0f0f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> PII;

 typedef map<int, int> MPS;

 const int maxn =  + ;

 vector<int> g[maxn];

 int vis[maxn];

 int dp[maxn][], val[maxn];

 void dfs(int u, int fa) {

     if(vis[u]) {

         if(dp[fa][] != dp[u][]) {

             dp[u][] = inf;

             if(!val[u]) {

                 dp[u][] = inf;

                 for(int i = ; i < sz(g[u]); i++) {

                     int v = g[u][i];

                     dfs(v, u);

                 }

             }

         }

         return;

     }

     vis[u] = ;

     dp[u][] = dp[fa][];

     dp[u][] = val[u] ? val[u] : dp[u][];

     for(int i = ; i < sz(g[u]); i++) {

         int v = g[u][i];

         dfs(v, u);

     }

 }

 int main() {

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         int m;

         scanf("%d%d", &val[i], &m);

         for(int j = ; j < m; j++) {

             int u;

             scanf("%d", &u);

             g[i].pb(u);

         }

     }

     vis[] = ;

     dp[][] = ;

     dp[][] = val[] ? val[] : ;

     for(int i = ; i < sz(g[]); i++) {

         int u = g[][i];

         dfs(u, );

     }

     for(int i = ; i <= n; i++) {

         if(dp[i][] == )

             cout << "sober ";

         else if(dp[i][] == inf)

             cout << "unknown ";

         else cout << dp[i][] << ' ';

         if(dp[i][] == )

             cout << "sober\n";

         else if(dp[i][] == inf)

             cout << "unknown\n";

         else cout << dp[i][] << endl;

     }

     return ;

 }

Problem C URAL 2014 Zhenya moves from parents

题意：共有n张收支凭据，根据当前的收到的凭据算出账户欠款，当前不足支出时，从账户扣除，收到一笔钱时把钱拿在手上不会去还信用卡上的钱，所以

信用卡欠款会越来越多的。

将时间离散化，排个序，然后以此建立线段树，每次将凭据对应的金额插入更新。线段树两个节点值，dep[rt]，表示当前区间时账户欠款，tot[rt]表示当前区间时能够剩下的现金。具体更新：

dep[rt] = dep[rt<<1] + min(0LL, tot[rt<<1]+dep[rt<<1|1]);
tot[rt] = tot[rt<<1|1] + max(tot[rt<<1]+dep[rt<<1|1], 0LL);

代码：

 #include <bits/stdc++.h>

 #define pb push_back

 #define mp make_pair

 #define esp 1e-8

 #define lowbit(x) ((x)&(-x))

 #define lson   l, m, rt<<1

 #define rson   m+1, r, rt<<1|1

 #define sz(x) ((int)((x).size()))

 #define pb push_back

 #define in freopen("solve_in.txt", "r", stdin);

 #define out freopen("solve_out.txt", "w", stdout);

 #define bug(x) printf("Line : %u >>>>>>\n", (x));

 #define inf 0x0f0f0f0f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> PII;

 typedef map<string, int> MPS;

 const int maxn =  + ;

 struct Node {

     int mon, day, h, mi, c, id;

     Node() {}

     Node(int mon, int day, int h, int mi, int c, int id):mon(mon), day(day), h(h), mi(mi), c(c), id(id) {}

     bool operator < (const Node &o)const {

         if(mon == o.mon) {

             if(day == o.day) {

                 if(h == o.h) return mi < o.mi;

                 return h < o.h;

             }

             return day < o.day;

         }

         return mon < o.mon;

     }

 } b[maxn];

 int a[maxn];

 char s[];

 int pos[maxn];

 LL dep[maxn<<], tot[maxn<<];

 void PushUp(int rt) {

     dep[rt] = dep[rt<<] + min(0LL, tot[rt<<]+dep[rt<<|]);

     tot[rt] = tot[rt<<|] + max(tot[rt<<]+dep[rt<<|], 0LL);

 }

 void update(int l, int r, int rt, int p, int c) {

     if(p == l && p == r) {

         if(c > )

             tot[rt] = c;

         else dep[rt] = c;

         return;

     }

     int m = (l+r)>>;

     if(p <= m)

         update(lson, p, c);

     else update(rson, p, c);

     PushUp(rt);

 }

 int main() {

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         int c, day, mon, h, mi;

         scanf("%d %d.%d %d:%d", &c, &day, &mon, &h, &mi);

         b[i] = Node(mon, day, h, mi, c, i);

         a[i] = c;

     }

     sort(b+, b+n+);

     for(int i = ; i <= n; i++)

         pos[b[i].id] = i;

     for(int i = ; i <= n; i++) {

         update(, n, , pos[i], a[i]);

         LL ans = dep[];

         printf("%I64d\n", ans);

     }

     return ;

 }

Problem F URAL 2017 Best of a bad lot

题意：有n个人处在不同的位置，声称目击哪些人也在场，这些人中有一些是嫌疑人，但是他们为了洗脱嫌疑会让他们的证词不相互矛盾，而其他人则会说出真正的情况。问最小的嫌疑团体。

分析：2个人所在地方不同，但是都目击同一个人，那么这两个人必定有一个为嫌疑人，很显然可以建立一个二分图，每次给图中结点着色，选取最少的加入到答案中。

代码：

 #include <bits/stdc++.h>

 #define pb push_back

 #define mp make_pair

 #define esp 1e-8

 #define lowbit(x) ((x)&(-x))

 #define lson   l, m, rt<<1

 #define rson   m+1, r, rt<<1|1

 #define sz(x) ((int)((x).size()))

 #define pb push_back

 #define in freopen("solve_in.txt", "r", stdin);

 #define out freopen("solve_out.txt", "w", stdout);

 #define bug(x) printf("Line : %u >>>>>>\n", (x));

 #define inf 0x0f0f0f0f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> PII;

 typedef map<string, int> MPS;

 const int maxn = ;

 typedef set<int> :: iterator IT;

 vector<int>g[maxn];

 set<int> a[maxn];

 vector<string> name;

 int vis[maxn];

 vector<int> tmp[];

 void dfs(int u, int col) {

     tmp[col].pb(u);

     vis[u] = ;

     for(int i = ; i < sz(g[u]); i++) {

         int v = g[u][i];

         if(vis[v]) continue;

         dfs(v, col^);

     }

 }

 int main() {

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         string str;

         cin >> str;

         name.pb(str);

         int m;

         scanf("%d", &m);

         for(int j = ; j < m; j++) {

             int k;

             scanf("%d", &k);

             a[i].insert(k);

         }

         a[i].insert(i);

     }

     for(int i = ; i <= n; i++) {

         for(int j = i+; j <= n; j++) {

             if(name[i-] != name[j-]) {

                 for(IT it = a[i].begin(); it != a[i].end(); it++)

                     if(a[j].count(*it)) {

                         g[i].pb(j);

                         g[j].pb(i);

                         break;

                     }

             }

         }

     }

     vector<int> ans;

     for(int i = ; i <= n; i++) {

         if(vis[i] || sz(g[i]) == ) continue;

         tmp[].clear();

         tmp[].clear();

         dfs(i, );

         if(tmp[].size() > tmp[].size()) tmp[] = tmp[];

         for(int j = ; j < sz(tmp[]); j++)

             ans.pb(tmp[][j]);

     }

     if(sz(ans)) {

         cout << sz(ans) << endl;

         for(int i = ; i < ans.size(); i++)

             printf("%d%c", ans[i], i == sz(ans)- ? '\n' : ' ');

     } else {

         puts("");

         puts("");

     }

     return ;

 }

Problem G URAL 2018 The Debut Album

题意：每个元素可以为1,或2，组成n个元素的排列，且连续1的个数不能超过a，连续2的个数不能超过b问有多少种方式.

分析：dp[now][0][len],表示当前位为1，前面已经有len个连续1了，

转移：dp[now][0][len] = dp[pre][0][len-1],len > 1

　　　dp[now][0][len] = sum{dp[pre][1][k]| 1 <= k <= b},len == 1

当前位为0时同理。

代码：

 #include <bits/stdc++.h>

 #define pb push_back

 #define mp make_pair

 #define esp 1e-8

 #define lowbit(x) ((x)&(-x))

 #define lson   l, m, rt<<1

 #define rson   m+1, r, rt<<1|1

 #define sz(x) ((int)((x).size()))

 #define pb push_back

 #define in freopen("solve_in.txt", "r", stdin);

 #define out freopen("solve_out.txt", "w", stdout);

 #define bug(x) printf("Line : %u >>>>>>\n", (x));

 #define inf 0x0f0f0f0f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> PII;

 typedef map<int, int> MPS;

 const int maxn =  + ;

 const int M = (int)1e9 + ;

 LL dp[][][];

 int main() {

     int n, a, b;

     scanf("%d%d%d", &n, &a, &b);

     dp[][][] = dp[][][] = ;

     for(int i = ; i <= n; i++) {

         int now = i&;

         int pre = ^now;

         for(int j = ; j <= a; j++) {

             dp[now][][j] = ;

             if(j == ) {

                 for(int k = ; k <= b; k++)

                     dp[now][][j] = (dp[now][][j] + dp[pre][][k])%M;

             } else

                 dp[now][][j] = (dp[now][][j] + dp[pre][][j-])%M;

         }

         for(int j = ; j <= b; j++) {

             dp[now][][j] = ;

             if(j == ) {

                 for(int k = ; k <= a; k++)

                     dp[now][][j] = (dp[now][][j] + dp[pre][][k])%M;

             } else

                 dp[now][][j] = (dp[now][][j] + dp[pre][][j-])%M;

         }

     }

     LL ans = ;

     int now = n&;

     for(int i = ; i <= a; i++)

         ans = (ans + dp[now][][i])%M;

     for(int i = ; i <= b; i++)

         ans = (ans + dp[now][][i])%M;

     cout << ans << endl;

     return ;

 }

Problem H URAL 2019 Pair: normal and paranormal

题意：括号匹配

分析：多重括号匹配，每种字母代表一个，A只能和a匹配。

代码：

Problem J URAL 2021 Scarily interesting!

题意：安排两个队伍n场比赛的得分，使得悬念保持的越长越好。

分析：赢的那方从小到大，另一方从大到小。

代码：

 #include <bits/stdc++.h>

 #define pb push_back

 #define mp make_pair

 #define esp 1e-8

 #define lowbit(x) ((x)&(-x))

 #define lson   l, m, rt<<1

 #define rson   m+1, r, rt<<1|1

 #define sz(x) ((int)((x).size()))

 #define pb push_back

 #define in freopen("solve_in.txt", "r", stdin);

 #define out freopen("solve_out.txt", "w", stdout);

 #define bug(x) printf("Line : %u >>>>>>\n", (x));

 #define inf 0x0f0f0f0f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> PII;

 typedef map<int, int> MPS;

 const int maxn = ;

 int a[maxn], b[maxn], r1[maxn], r2[maxn];

 bool cmp1(int x, int y) {

     return a[x] > a[y];

 }

 bool cmp2(int x, int y) {

     return b[x] > b[y];

 }

 int main() {

     int n;

     scanf("%d", &n);

     int sum1 = , sum2 = ;

     for(int i = ; i <= n; i++) {

         scanf("%d", &a[i]);

         sum1 += a[i];

         r1[i] = i;

     }

     for(int i = ; i <= n; i++) {

         scanf("%d", b+i);

         sum2 += b[i];

         r2[i] = i;

     }

     sort(r1+, r1+n+, cmp1);

     sort(r2+, r2+n+, cmp2);

     if(sum1 > sum2) {

         for(int i = ; i <= n; i++)

             printf("%d %d\n", r1[n+-i], r2[i]);

     } else if(sum1 < sum2) {

         for(int i = ; i <= n; i++)

             printf("%d %d\n", r1[i], r2[n+-i]);

     } else {

         for(int i = ; i <= n; i++)

             printf("%d %d\n", i, i);

     }

     return ;

 }

巴特西

NEERC 2014, Eastern subregional contest

最新文章

热门文章