Codeforces-542div2

https://www.cnblogs.com/31415926535x/p/10468017.html
codeforces-1130A~G
チームメイトと一連の問題をしましたが、
A. Be Positive
に言及
各数が除算された正数の個数が(lceilfrac{n}{2}rceil)以上になるように除数を見つけるには、
ぶんせき
すべての正数、負数の個数を統計して、、正数の多いその除数は1で、負数の多いのは-1です
コード#コード#

//cf
#include 
//#include 
//#include 
//#include 
//#include 
//#include 
#define aaa cout<<233< pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
int a[maxn];
int main()
{
//    freopen("233.in" , "r" , stdin);
//    freopen("233.out" , "w" , stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; ++i)cin >> a[i];
    sort(a + 1, a + 1 + n);
    int nump = 0;
    int numn = 0;
    for(int i = 1; i <= n; ++i)
        if(a[i] > 0)
            ++nump;
        else if(a[i] < 0)
            ++numn;
    if(nump >= (n + 1) / 2)
        cout << 1 << endl;
    else if(numn >= (n + 1) / 2)
        cout << -1 << endl;
    else
        cout << 0 << endl;
    return 0;
}

B. Two Cakes
に言及
2つのグループ1~nの数からなるシーケンスを意味し、一人一人が1つのグループを選択し、費用は2つのツリーの間の距離で、それから総距離の最小はいくらですか、
ぶんせき
私は最初は一人の選択を最も少なく処理することに貪欲だと思っていましたが、それに残りの人を加えて、それからwaになりました.なぜなら、今回の選択と次の選択の距離と最小であることを保証していないので、解決方法は二つ一緒に処理して、それぞれの選択の状況を考えて、このように最小を取ればいいのです.
コード#コード#

//cf
#include 
//#include 
//#include 
//#include 
//#include 
//#include 
#define aaa cout<<233< pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;
const ll mod = 1e9 + 7;
int a[maxn][2];
bool flag[maxn];
int main()
{
//    freopen("233.in" , "r" , stdin);
//    freopen("233.out" , "w" , stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin >> n;
    int t;
    memset(flag, false, sizeof flag);
    for(int i = 1; i <= 2 * n; ++i)
    {
        cin >> t;
        if(!flag[t])
        {
            a[t][0] = i;
            flag[t] = true;
        }
        else
            a[t][1] = i;
    }
    ll ans = a[1][0] + a[1][1] - 2;
    for(int i = 1; i <= n - 1; ++i)
    {
        int p = abs(a[i + 1][0] - a[i][0]) + abs(a[i + 1][1] - a[i][1]);
        int q = abs(a[i + 1][0] - a[i][1]) + abs(a[i + 1][1] - a[i][0]);
        ans += min(p, q);
    }
    cout << ans << endl;
    return 0;
}

C. Connect
に言及
地図をあげて、その中の陸地は0で、水は1で、それからあなたに1つの起点の1つの終点をあげて、あなたは任意の2つの陸地の上で1本のトンネルを建ててこの2つの陸地を通じさせることができて、それからあなたに起点から終点まで必要なトンネルの最小の長さを聞いて、
ぶんせき
トンネルは1本しか建てられないので、起点のある陸地と終点のある陸地が通じなければ、このトンネルは必ずこの2つの陸地の間にあり、データ量は大きくなく、この2つの陸地の点を直接列挙し、最小の距離を取ればいいのですが、、、
一つの点が起点や終点にある陸地で現用できるかどうかを判断し、地図を「染色」することで、列挙することができ、、、
コード#コード#

//cf
#include 
//#include 
//#include 
//#include 
//#include 
//#include 
#define aaa cout<<233< pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
int fa[maxn];
int _find(int x)
{
    if(fa[x] == x)return x;
    return fa[x] = _find(fa[x]);
}
void _union(int x, int y)
{
    int f1 = _find(x);
    int f2 = _find(y);
    if(f1 != f2)fa[f1] = f2;
    else        fa[f2] = f1;
}
int mp[60][60];
int solve(int i, int j, int n)
{
    int x1 = i / n;
    int y1 = i - x1 * n;
    int x2 = j / n;
    int y2 = j - x2 * n;
    if(y1 == 0)
    {
        y1 = n;
        --x1;
    }
    if(y2 == 0)
    {
        y2 = n;
        --x2;
    }
//    cout << x1 << y1 << x2 << y2 << endl;
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main()
{
//    freopen("233.in" , "r" , stdin);
//    freopen("233.out" , "w" , stdout);
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);cout.tie(0);
    int n;scanf("%d", &n);
    int x1, x2, y1, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    for(int i = 1; i <= n; ++i)
    {
        getchar();
        for(int j = 1; j <= n; ++j)
            mp[i][j] = (int)(getchar() - '0');

    }

    for(int i = n + 1; i <= n + 1 + n * n; ++i)fa[i] = i;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(mp[i - 1][j] == mp[i][j] && i - 1 >= 1)
                _union(i * n + j, (i - 1) * n + j);
            if(mp[i + 1][j] == mp[i][j] && i + 1 <= n)
                _union(i * n + j, (i + 1) * n + j);
            if(mp[i][j + 1] == mp[i][j] && j + 1 <= n)
                _union(i * n + j, i * n + j + 1);
            if(mp[i][j - 1] == mp[i][j] && j - 1 >= 1)
                _union(i * n + j, i * n + j - 1);
        }
    }
//    for(int i = 1; i <=n; ++i)
//    {
//        for(int j = 1; j <= n; ++j)
//            cout << _find(i * n + j) << " ";
//        cout << endl;
//    }
    int s = _find(x1 * n + y1);
    int t = _find(x2 * n + y2);
//    cout << s << t << endl;
    int ans = inf;
    for(int i = n + 1; i <= n + 1 + n * n; ++i)
    {
        for(int j = 1 + n; j <= n + 1 + n * n; ++j)
        {
            if(_find(i) == s && _find(j) == t)
            {
                ans = min(ans, solve(i, j, n));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

D1. Toy Train
に言及
つの環状の鉄道から、上にnつの駅があって、すべての駅にいくつかのキャンディがあって、これらのキャンディは(b_i)その駅まで運んで、、、列車は1つの駅で1つのキャンディを引くことしかできなくて、しかし任意のキャンディを置くことができて、、、、あなたにこのnつの駅からすべてのキャンディを発送するのに必要な最小限の時間を聞いて、
ぶんせき
毎回1つのキャンディしか上がらなくて、、、最后に降りたキャンディはキャンディの数が最も多い駅のもので、、この駅から出発して最も费用のかかる别の駅を探して、このようにその駅のすべてのキャンディを送り终わった时に他の駅のキャンディをついでにも送り终わって、、、
それぞれの駅iを列挙して、駅iに対してすべての他の駅を列挙して、すべての時間の中の最大値を求めるのはこの駅が使った時間で、、、
リファレンス
コード#コード#

//cf
#include 
//#include 
//#include 
//#include 
//#include 
//#include 
#define aaa cout<<233< pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;
const ll mod = 1e9 + 7;
struct node
{
    int num;
    int mi;
}node[maxm];
int n, m;
int getdis(int i, int j)
{
    //get the dis of i -> j
    if(i <= j)return j - i;
    else      return n - i + j;
}
int solve(int loc)
{
    //find the furthest and the most candies node
    int fur = loc;
    int num = node[loc].num;
    int ans = 0;
    int dis;
    for(int i = loc; i <= n; ++i)
    {
        if(node[i].mi == inf)continue;
        dis = getdis(loc, i) + (node[i].num - 1) * n + node[i].mi;
        ans = max(ans, dis);
    }
    for(int i = 1; i <= loc - 1; ++i)
    {
        if(node[i].mi == inf)continue;
        dis = getdis(loc, i) + (node[i].num - 1) * n + node[i].mi;
        ans = max(ans, dis);
    }
//    for(int i = loc; i <= n; ++i)
//    {
//        if(node[i].num >= num)
//        {
//            fur = i;
//            num = node[i].num;
//        }
//    }
//    for(int i = 1; i <= loc - 1; ++i)
//    {
//        if(node[i].num >= num)
//        {
//            fur = i;
//            num = node[i].num;
//        }
//    }
//    cout << fur << " ";
//    int ans = n * (node[fur].num - 1);
//    ans += getdis(loc, fur);
//    ans += getdis(fur, node[fur].mi);
    return ans;
}
int main()
{
//    freopen("233.in" , "r" , stdin);
//    freopen("233.out" , "w" , stdout);
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    int a, b;
    for(int i = 1; i <= n; ++i)node[i].mi = inf;
    for(int i = 1; i <= n; ++i)node[i].num = 0;
    for(int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        ++node[a].num;
        if(getdis(a, b) <= node[a].mi)
            node[a].mi = getdis(a, b);
    }
    for(int i = 1; i <= n; ++i)
        cout << solve(i) << " ";
    cout << endl;
//    for(int i = 1; i <= n; ++i)
//    {
//        cout << i << " ";
//        cout << solve(i) << endl;
//    }
    return 0;
}

E. Wrong Answer
に言及
1つの数列で最大の区間を求め、区間の長さを乗じて、
彼が与えたアルゴリズムは前の区間と負数が現れると捨てられ、最後の答えに及ぼす長さの影響を考慮しなかった.
問題は私たちに1つの数列を構築して、この数列の正しい答えがそのやり方より算出した結果が大きいようにしますk
ぶんせき
前の1998個はすべて0で、後ろの1個の数は-pで、1個の時p+q,,
このように正しい答えは(2000 q)、彼が算出した答えは(p+q)、
大きいkにするには、(2000 q-(p+q)=k)、つまり(q=frac{p+k}{1999}),,p,qがすべて整数であることを保証するために、,,,(p=1999-k%1999)を設定し、このように算出したqが整数であり、,

//cf
#include 
//#include 
//#include 
//#include 
//#include 
//#include 
#define aaa cout<<233< pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;
const ll mod = 1e9 + 7;

int main()
{
//    freopen("233.in" , "r" , stdin);
//    freopen("233.out" , "w" , stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k; cin >> k;
    cout << 2000 << endl;
    for(int i = 1; i <= 2000 - 2; ++i)cout << 0 << " ";
    int p = 1999 - k % 1999;
    cout << -p << " " << ((k + p) / 1999 + p) << endl;
    return 0;
}

(end)