B

Vika有n种颜料,每种有$a_i$份,其要依此为一无限长区间上色,每次占一个单位,直到一种颜料全部用完。选择首先使用那种颜料,从该颜料开始依此选择下一个颜料,求染色区间的最长长度。

模拟

很明显这个位置在$a_i$最小位置的后一个,这样至少扫描mn*n次,若有多个最小位置,则选择两个最小位置件间隔最长的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 4e5 + 10;
const int INF = 0x3f3f3f3f;
int a[maxn],n;

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&n);
int mn = INF;
for(int i=0;i<n;++i) scanf("%d",a+i),a[i+n] = a[i],mn = min(mn,a[i]);
int len = 0,lst = -1;
for(int i=0;i<2*n;++i)
{
if(a[i] == mn)
{
len = max(len,i - lst-1);
lst = i;
}
}
printf("%lld\n",(LL)mn*n+(LL)len);
return 0;
}

C

输入k,输出一个$(2^k)^2$的矩阵,每行描述一个$2^k$的向量(且不重复),使其满足向量两两间点积为0
+表示 +1 -表示 -1

构造

我们可以从上一个状态递推过来,因为当前状态总可以由四个上一个状态的变换表示。
上一个状态为A,上一个状态取反为B,则当前状态可以表示为

AA
BA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

string cal(string s)
{
string res = "";
for(int i=0;i<s.size()/2;++i)
if(s[i] == '+') res += '*';
else res += '+';
for(int i=s.size()/2;i<s.size();++i)
if(s[i] == '+') res += '+';
else res += '*';
return res;
}


int main()
{
//freopen("test.txt","r",stdin);
int n;
string s[10][1000];

s[2][0]="++**";
s[2][1]="+*+*";
s[2][2]="++++";
s[2][3]="+**+";


scanf("%d",&n);
if(n == 0)
{
puts("*");
return 0;
}
if(n == 1)
{
puts("++");
puts("+*");
return 0;
}
if(n == 2)
{
for(int i=0;i<4;++i) puts(s[n][i].c_str());
return 0;
}
for(int i=3;i<=9;++i)
{
int n = i;
int m = pow(2,n-1);
for(int i=0;i<m;++i)
{
s[n][i] = s[n-1][i] + s[n-1][i];
}
for(int i=0;i<m;++i)
{
s[n][i+m] = cal(s[n][i]);
}
}
for(int i=0;i<pow(2,n);++i) puts(s[n][i].c_str());
return 0;
}

D

读入n组x1,y1,x2,y2,更新[(x1,y1),(x2,y2)]间的单位,求最后覆盖的单位

线段树维护矩形面积并

模板题,注意读入不是按照矩形的左上角右下角给的,还有要对右下角进行++操作

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define pb push_back

const int maxn = 1e5 + 10;
struct Edge{
    int x,y1,y2,in;
    Edge(int x,int y1,int y2,int in):x(x),y1(y1),y2(y2),in(in) {}
    bool operator<(const Edge& rhs) const{
        return x < rhs.x;
    }
};

struct Node{
    int cnt;
    LL    len;
    Node() { cnt = len = 0; }
} p[maxn<<3];

vector<Edge> save;
vector<int> point;

void pushup(int L,int R,int u)
{
    if(p[u].cnt) p[u].len = point[R+1] - point[L];
    else if(L == R) p[u].len = 0;
    else p[u].len = p[u<<1].len + p[u<<1|1].len;
}

void update(int cL,int cR,int add,int L,int R,int u)
{
    if(cL <= L && R <= cR)
    {
        p[u].cnt += add;
    }
    else
    {
        int m = (L+R)>>1;
        if(m >= cL) update(cL,cR,add,L,m,u<<1);
        if(m < cR) update(cL,cR,add,m+1,R,u<<1|1);
    }
    pushup(L,R,u);
}

int main()
{
    //freopen("test.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        if(x1 > x2) swap(x1,x2);
        if(y1 > y2) swap(y1,y2);
        ++x2; ++y2;
        save.pb(Edge(x1,y1,y2,1));
        save.pb(Edge(x2,y1,y2,-1));
        point.pb(y1);
        point.pb(y2);
    }
    sort(save.begin(),save.end());
    sort(point.begin(),point.end());
    int pn = unique(point.begin(),point.end()) - point.begin();
    LL res = 0;
    for(int i=0;i<save.size() - 1;++i)
    {
        int L = lower_bound(point.begin(),point.begin() + pn,save[i].y1) - point.begin();
        int R = lower_bound(point.begin(),point.begin() + pn,save[i].y2) - point.begin() - 1;
        if(L <= R) update(L,R,save[i].in,0,pn-1,1);
        res += p[1].len*(save[i+1].x - save[i].x);
    }
    printf("%lld\n",res);
    return 0;
}