2013-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

多Case的题注意清0


{{{
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
long long x[300000], y[300000], sumx[300000], sumy[300000];
bool check(int i, int j, int k)
{
    return ((x[k] - x[i]) * (y[j] - y[i]) - (y[k] - y[i]) * (x[j] - x[i])) < 0;
}
long long calc(int i, int j)
{
    return sumx[j] * y[i] - sumy[j] * x[i];
}
int b[400000];
long long f[300000], g[300000];
int main()
{
    int n, i, w, tmp, j, k;
    vector<int> ans;
    while (cin >> n) {
        if (n == 0) break;
        for (i = 1; i <= n; i ++) {
            scanf("%d%d", &j, &k);
                        x[i] = k; y[i] = j;
                    }
        sumx[n + 1] = sumy[n + 1] = 0;
        for (i = n; i >= 1; i --) {
            sumx[i] = sumx[i + 1] + x[i];
            sumy[i] = sumy[i + 1] + y[i];
        }
          w = 0; tmp = 1;
        for (i = 1; i <= n - 1; i ++) {
            while (w > 1 && check(b[w - 1], b[w], i)) w --;
            b[++w] = i; 
            if (tmp > w) tmp = w;
            while (tmp < w && calc(b[tmp + 1], i + 1) > calc(b[tmp], i + 1)) tmp ++;
            while (tmp > 1 && calc(b[tmp - 1], i + 1) > calc(b[tmp], i + 1)) tmp --;
            f[i] = calc(b[tmp], i + 1); 
        }
        w = 0; tmp = 1;
        for (i = n; i > 1; i --) {
            while (w > 1 && check(b[w - 1], b[w], i)) w --;
            b[++w] = i;
            if (tmp > w) tmp = w;
            while (tmp < w && calc(b[tmp + 1], i) < calc(b[tmp], i)) tmp ++;
            while (tmp > 1 && calc(b[tmp - 1], i) < calc(b[tmp], i)) tmp --;
            g[i] = calc(b[tmp], i);
        }
        ans.clear();
        for (i = 1; i <= n - 1; i ++)
            if (g[i + 1] < f[i]) ans.push_back(i);
        printf("%d\n", ans.size());
        for (i = 0; i < ans.size(); i ++)
            printf("%d\n", ans[i]);
    }
     return 0;
}
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int mo = 1000000007;
int tims[110000], sum[110000], sum1[110000];
char a[110000], b[110000];
int ansi, n;
bool ansf;
int work(int i, bool flag)
{   
    int ret;
//  cout << i << " " << flag << endl;
    if (a[i] != '?' && b[i] != '?' && a[i] == b[i]) return 0;
    if (a[i] == '?' && b[i] == '?') {ansi = i; ansf = flag; return tims[sum[i - 1]]; }
       else {
           if (a[i] == '1' || b[i] == '0') flag = !flag;
           if (sum[i - 1] > 0) { ansi = i; ansf = flag; return tims[sum[i - 1] - 1]; }
              else if ((sum1[i - 1] & 1) == flag) { ansi = i; ansf = flag; return 1; }
          }
    return 0;
}
bool print()
{
    bool flag = ansf;
    int tt, i;
    a[ansi + 1] = '1';
    for (i = ansi + 2; i < n; i ++) a[i] = '0';
    if (a[i] == '1' || b[i] == '0') flag = !flag;
    tt = 0;
    if (sum1[ansi - 1] != flag) tt = 1;
    if (tt && sum[ansi - 1] == 0) return 0;
    for (i = 0; i < ansi; i ++) 
           if (a[i] == '?' && b[i] == '?') { a[i] = tt; if (tt) tt --;  }
          else if (a[i] == '?') a[i] = b[i];
    for (i = 0; i < n; i ++) printf("%c", a[i]);
    cout << endl;
    for (i = 0; i < n; i ++) 
        if (i != ansi) printf("%c", a[i]);
        else if (a[i] == '1') printf("0");
          else printf("1");
    printf("\n");
    return 1;
}

int main()
{
    int tt, i, l, n1, tmp, cas = 0;
    long long ans;
    tims[0] = 1;
    for (i = 1; i <= 110000; i ++) tims[i] = 2 * tims[i - 1] % mo;
    cin >> tt;
    while (tt --) {
        scanf("%s", a);
        scanf("%s", b);
        printf("Case #%d:\n", ++cas);
        n = strlen(a);
        sum[0] = 0; n1 = 0; sum1[0] = 0;
        for (i = 0; i < n; i ++) {
            if (i > 0) sum[i] = sum[i - 1];
            if (i > 0) sum1[i] = sum1[i - 1];
            if (a[i] == '?' && b[i] == '?') sum[i] ++;
            else if (a[i] == '?') sum1[i] += b[i] == '1';
            else if (b[i] == '?') sum1[i] += a[i] == '1';
              else if (a[i] != b[i]) { n1 ++; l = i; }
            else sum1[i] += a[i] == '1';
        //  cout << "#" << sum[i] << " " << sum1[i] << endl;
        }
        ans = 0; //cout << l << endl;
            if (n1 > 1) { printf("Impossible\n"); continue; }
        if (n1 == 1) {
            if (l < n - 1) {
            if (a[l + 1] == '?' && b[l + 1] == '?') tmp = 0;
               else {
                   if (a[l + 1] == '0' || b[l + 1] == '0')  { printf("Impossible\n"); continue; }
                   tmp = 1;
               }
            for (i = l + 2; i < n; i ++) if (sum1[i] != sum1[l] + tmp) break;
            if (i != n) { printf("Impossible\n"); continue; }
            }
            //if (i != n) { printf("Impossible\n"); continue; }
            if (l == n - 1) ans += work(n - 1, 0);
            else ans += work(l, 0);
            }
        else {
            if (a[n - 1] == '?' || b[n - 1] == '?') ans += work(n - 1, 0);
            //cout <<n - 1 << " " <<  ans << endl;
            for (i = n - 1; i > 0; i--) {
                  if (sum[i] != sum[n - 1]) break;
                 else if (a[i] == '?' && b[i] == '?' || sum[i] - sum[i - 1] == 1) ans += work(i - 1, 0);
                // cout << i << " " << ans << endl;
            }
        }
        ans %= mo;
        if (ans != 1) cout <<"Ambiguous " << ans << endl;
        else {
            if (a[ansi] == '?' && b[ansi] == '?') {
                a[ansi] = '0'; if (print()) continue;
                a[ansi] = '1'; print();
            }
             else   print();
        }
    }
    return 0;
}
}}}

多Case的题注意清0

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
long long x[300000], y[300000], sumx[300000], sumy[300000];
bool check(int i, int j, int k)
{
    return ((x[k] - x[i]) * (y[j] - y[i]) - (y[k] - y[i]) * (x[j] - x[i])) < 0;
}
long long calc(int i, int j)
{
    return sumx[j] * y[i] - sumy[j] * x[i];
}
int b[400000];
long long f[300000], g[300000];
int main()
{
    int n, i, w, tmp, j, k;
    vector<int> ans;
    while (cin >> n) {
        if (n == 0) break;
        for (i = 1; i <= n; i ++) {
            scanf("%d%d", &j, &k);
                        x[i] = k; y[i] = j;
                    }
        sumx[n + 1] = sumy[n + 1] = 0;
        for (i = n; i >= 1; i --) {
            sumx[i] = sumx[i + 1] + x[i];
            sumy[i] = sumy[i + 1] + y[i];
        }
          w = 0; tmp = 1;
        for (i = 1; i <= n - 1; i ++) {
            while (w > 1 && check(b[w - 1], b[w], i)) w --;
            b[++w] = i; 
            if (tmp > w) tmp = w;
            while (tmp < w && calc(b[tmp + 1], i + 1) > calc(b[tmp], i + 1)) tmp ++;
            while (tmp > 1 && calc(b[tmp - 1], i + 1) > calc(b[tmp], i + 1)) tmp --;
            f[i] = calc(b[tmp], i + 1); 
        }
        w = 0; tmp = 1;
        for (i = n; i > 1; i --) {
            while (w > 1 && check(b[w - 1], b[w], i)) w --;
            b[++w] = i;
            if (tmp > w) tmp = w;
            while (tmp < w && calc(b[tmp + 1], i) < calc(b[tmp], i)) tmp ++;
            while (tmp > 1 && calc(b[tmp - 1], i) < calc(b[tmp], i)) tmp --;
            g[i] = calc(b[tmp], i);
        }
        ans.clear();
        for (i = 1; i <= n - 1; i ++)
            if (g[i + 1] < f[i]) ans.push_back(i);
        printf("%d\n", ans.size());
        for (i = 0; i < ans.size(); i ++)
            printf("%d\n", ans[i]);
    }
     return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int mo = 1000000007;
int tims[110000], sum[110000], sum1[110000];
char a[110000], b[110000];
int ansi, n;
bool ansf;
int work(int i, bool flag)
{   
    int ret;
//  cout << i << " " << flag << endl;
    if (a[i] != '?' && b[i] != '?' && a[i] == b[i]) return 0;
    if (a[i] == '?' && b[i] == '?') {ansi = i; ansf = flag; return tims[sum[i - 1]]; }
       else {
           if (a[i] == '1' || b[i] == '0') flag = !flag;
           if (sum[i - 1] > 0) { ansi = i; ansf = flag; return tims[sum[i - 1] - 1]; }
              else if ((sum1[i - 1] & 1) == flag) { ansi = i; ansf = flag; return 1; }
          }
    return 0;
}
bool print()
{
    bool flag = ansf;
    int tt, i;
    a[ansi + 1] = '1';
    for (i = ansi + 2; i < n; i ++) a[i] = '0';
    if (a[i] == '1' || b[i] == '0') flag = !flag;
    tt = 0;
    if (sum1[ansi - 1] != flag) tt = 1;
    if (tt && sum[ansi - 1] == 0) return 0;
    for (i = 0; i < ansi; i ++) 
           if (a[i] == '?' && b[i] == '?') { a[i] = tt; if (tt) tt --;  }
          else if (a[i] == '?') a[i] = b[i];
    for (i = 0; i < n; i ++) printf("%c", a[i]);
    cout << endl;
    for (i = 0; i < n; i ++) 
        if (i != ansi) printf("%c", a[i]);
        else if (a[i] == '1') printf("0");
          else printf("1");
    printf("\n");
    return 1;
}
int main()
{
    int tt, i, l, n1, tmp, cas = 0;
    long long ans;
    tims[0] = 1;
    for (i = 1; i <= 110000; i ++) tims[i] = 2 * tims[i - 1] % mo;
    cin >> tt;
    while (tt --) {
        scanf("%s", a);
        scanf("%s", b);
        printf("Case #%d:\n", ++cas);
        n = strlen(a);
        sum[0] = 0; n1 = 0; sum1[0] = 0;
        for (i = 0; i < n; i ++) {
            if (i > 0) sum[i] = sum[i - 1];
            if (i > 0) sum1[i] = sum1[i - 1];
            if (a[i] == '?' && b[i] == '?') sum[i] ++;
            else if (a[i] == '?') sum1[i] += b[i] == '1';
            else if (b[i] == '?') sum1[i] += a[i] == '1';
              else if (a[i] != b[i]) { n1 ++; l = i; }
            else sum1[i] += a[i] == '1';
        //  cout << "#" << sum[i] << " " << sum1[i] << endl;
        }
        ans = 0; //cout << l << endl;
            if (n1 > 1) { printf("Impossible\n"); continue; }
        if (n1 == 1) {
            if (l < n - 1) {
            if (a[l + 1] == '?' && b[l + 1] == '?') tmp = 0;
               else {
                   if (a[l + 1] == '0' || b[l + 1] == '0')  { printf("Impossible\n"); continue; }
                   tmp = 1;
               }
            for (i = l + 2; i < n; i ++) if (sum1[i] != sum1[l] + tmp) break;
            if (i != n) { printf("Impossible\n"); continue; }
            }
            //if (i != n) { printf("Impossible\n"); continue; }
            if (l == n - 1) ans += work(n - 1, 0);
            else ans += work(l, 0);
            }
        else {
            if (a[n - 1] == '?' || b[n - 1] == '?') ans += work(n - 1, 0);
            //cout <<n - 1 << " " <<  ans << endl;
            for (i = n - 1; i > 0; i--) {
                  if (sum[i] != sum[n - 1]) break;
                 else if (a[i] == '?' && b[i] == '?' || sum[i] - sum[i - 1] == 1) ans += work(i - 1, 0);
                // cout << i << " " << ans << endl;
            }
        }
        ans %= mo;
        if (ans != 1) cout <<"Ambiguous " << ans << endl;
        else {
            if (a[ansi] == '?' && b[ansi] == '?') {
                a[ansi] = '0'; if (print()) continue;
                a[ansi] = '1'; print();
            }
             else   print();
        }
    }
    return 0;
}