《 Codeforces Round #673 (Div. 2)》

A：签到：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1005;
const int M = 1e6+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;

int a[N];
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        int n,k;n = read(),k = read();
        priority_queue<int,vector<int>,greater<int> > Q;
        while(n--)
        {
            int x;x = read();
            Q.push(x);
        }
        int num = 0;
        while(Q.size() > 1)
        {
            int ma1 = Q.top();Q.pop();
            int ma2 = Q.top();Q.pop();
            if(ma1+ma2 > k) break;
            num++;
            Q.push(ma1);
            Q.push(ma1+ma2);
        }
        printf("%d
",num);
    }
    //system("pause");
    return 0;
}

View Code

B：签到：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int M = 2e5+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;

int a[N];
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        int n,T;n = read(),T = read();
        for(rg int i = 1;i <= n;++i) a[i] = read();
        if(T&1)
        {
            for(rg int i = 1;i <= n;++i) a[i] = (a[i] <= T/2) ? 0 : 1;
        }
        else
        {
            int f = 0;
            for(rg int i = 1;i <= n;++i)
            {
                if(a[i] == T/2) a[i] = f,f = (f+1) % 2;
                else a[i] = (a[i] < T/2) ? 0 : 1;
            }
        }
        for(rg int i = 1;i <= n;++i) printf("%d%c",a[i],i == n ? '
' : ' ');
    }
   // system("pause");
}

View Code

C：处理出每个数组覆盖完的最大距离，然后取最小。

有点抽象，见代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<double,int> pii;
const int N = 3e5+5;
const int M = 2e5+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;

int a[N],ans[N];
vector<int> vec[N];
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        int n;n = read();
        for(rg int i = 1;i <= n;++i) vec[i].clear();
        for(rg int i = 1;i <= n;++i)
        {
            int x;x = read();
            vec[x].push_back(i);
            ans[i] = INF;
        }
        for(rg int i = 1;i <= n;++i)
        {
            if(!vec[i].empty())
            {
                int mx = vec[i][0],len = vec[i].size();
                for(rg int j = 1;j < len;++j)
                {
                    mx = max(mx,vec[i][j]-vec[i][j-1]);
                }
                mx = max(mx,n-vec[i][len-1]+1);
                ans[mx] = min(ans[mx],i);
            }
        }
        for(rg int k = 2;k <= n;++k) ans[k] = min(ans[k],ans[k-1]);
        for(rg int k = 1;k <= n;++k) printf("%d%c",ans[k] == INF ? -1 : ans[k],k == n ? '
' : ' ');
    }
}

View Code

D：感觉这题也不是很难想到。

一开始没注意题，以为过程中出现负数也可以。

那么就可以一直用第一个来操作。

对于然后使别的数分为 > 平均数和 < 平均数来操作。

后面，发现中间不能出现负数。。

那么，我们就先把所有的值都加给1，然后最后全部给每个位即可。

这里如果这个位子满足a[i] % i == 0，那么显然可以直接给1号位。

如果不满足，那么就先用1号位来凑成满足的，然后再给一号位。

因为我们是边给边凑的，且a[i] >= 1，那么这个凑得值肯定 < i,对于前面的i个位置相加后的值显然>= i-1，那么中途肯定不会有负数出现。

所以是可行的。（笨比的我还用exgcd求加的值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<double,int> pii;
const int N = 1e4+5;
const int M = 1e5+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;

int a[N];
struct Node{int i,j,x;};
vector<Node> vec;
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        int n;n = read();
        vec.clear();
        int sum = 0;
        for(rg int i = 1;i <= n;++i) a[i] = read(),sum += a[i];
        if(sum % n != 0){printf("-1
");continue;}
        int ma = sum / n;
        for(rg int i = 2;i <= n;++i)
        {
            if(a[i] % i == 0) vec.push_back(Node{i,1,a[i]/i});
            else
            {
                int ma = (i - a[i] % i);
                vec.push_back(Node{1,i,ma});
                vec.push_back(Node{i,1,(a[i]+ma) / i});
            }
        }
        for(rg int i = 2;i <= n;++i) vec.push_back(Node{1,i,ma});
        printf("%d
",vec.size());
        for(rg int i = 0;i < vec.size();++i) printf("%d %d %d
",vec[i].i,vec[i].j,vec[i].x);
    }
}

View Code