1181 B
题意
一个高精整数，要把它从中间割开分成两部分，每一部分不能为空也不能有前导零，问如何才能使得两部分的和最小。
Examples
input
7
1234567
output
1801
input
3
101
output
11
解
打高精好点烦的
就均分成两半，再判一判前导零就好了。
1181 C
题意
旗帜的定义：
这些是旗帜：
这些不是旗帜：
现在给你一个英文字母矩阵，问有多少个子矩形是旗帜。 ((n,mle 1000))
Examples
input
4 3
aaa
bbb
ccb
ddd
output
6
input
6 1
a
a
b
b
c
c
output
1
input
4 3
aca
ccc
bbb
aaa
output
8
解
弄一个双端队列模拟即可。
细节较多。
Code
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#include<bits/stdc++.h> using namespace std; typedef pair<char,int> P; const int maxn=1003,INF=1050000000; char s[maxn]; int n,m; long long ans; deque<P> a[maxn]; bool valid(const deque<P> &q){ return q.size()==3&&q[0].second>=q[1].second&&q[1].second==q[2].second; } bool equal(const deque<P> &q1,const deque<P> &q2){ if(q2.size()!=3)return 0; for(int i=0;i<=2;i++)if(q1[i].first!=q2[i].first)return 0; return q1[1].second==q2[1].second&&q1[2].second==q2[2].second; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s+1); for(int j=1;j<=m;j++){ if(a[j].size()>=1&&a[j].back().first==s[j])a[j].back().second++; else a[j].push_back(P(s[j],1)); while(a[j].size()>=2&&a[j].back().second>a[j][a[j].size()-2].second)a[j].pop_front(); if(a[j].size()>=4)a[j].pop_front(); } for(int l=1,r=1;r<=m;l=r){ for(;l<=m&&!valid(a[l]);l++); for(r=l;r<=m&&valid(a[r])&&equal(a[l],a[r]);r++); ans+=(long long)(r-l)*(r-l+1)/2; } } printf("%lldn",ans); return 0; }
1181 D
题意
有 (m) 个城市，每年举办比赛。在最先的 (n) 年中比赛的举办地是已知的，后来制定了规则，每年以每个城市之前举办次数为第一关键字，以每个城市的编号为第二关键字，选择最小的城市举办比赛。现在有 (q) 个询问，每次询问第 (x_i) 年由哪个城市举办。 ((1le n,m,qle 5*10^5,x_ile 10^{18}))
Examples
input
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16
output
4
3
4
2
3
4
1
2
3
4
input
4 5 4
4 4 5 1
15
9
13
6
output
5
3
3
3
解
模拟发现，经过 (O(n^2)) 年，举办城市必定会变成 (1,2,dots ,m) 的顺序。
因此，在临界值之后的询问很容易得出结果。
在临界值之前的询问呢？
考虑将每个城市按上述两个关键字排序，然后对于每个第一关键字相等的区间设它们为 ([l_i...r_i](r_i+1=l_{i+1},l_1=1)) 我们发现举办城市的顺序就是：
- (1) 到 (r_1) 轮流，进行 (cnt[l_2]-cnt[1]) 遍；
- (dots)
- (1) 到 (r_{i+1}) 轮流，进行 (cnt[l_{i+2}]-cnt[l_{i+1}]) 遍；
- (dots)
- (1) 到 (r_{k-1}) 轮流，进行 (cnt[l_k]-cnt[l_{k-1}]) 遍；
- (1) 到 (m) 轮流，进行 (∞) 遍（这是临界值之后）。
每次相当于一轮轮完之后把 ([1,r_i]) 与 ([l_{i+1},r_{i+1}]) 合并。
(n^2) 归并显然是不行的，因此我们用一种数据结构来实现每个城市的名次查询。
Code
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#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<long long,int> QQ; const int maxn=500003,INF=1050000000; P a[maxn]; QQ q[maxn]; int n,m,Q,ans[maxn],t[maxn<<2]; int mod(long long x,int y){return x%y==0?y:x%y;} void change(int p,int l,int r,int pos){ if(l==r){ t[p]++; return; } int mid=(l+r)>>1; if(pos<=mid)change(p<<1,l,mid,pos); else change(p<<1|1,mid+1,r,pos); t[p]=t[p<<1]+t[p<<1|1]; } int kth(int p,int l,int r,int rnk){ if(l==r)return l; int mid=(l+r)>>1; if(rnk<=t[p<<1])return kth(p<<1,l,mid,rnk); else return kth(p<<1|1,mid+1,r,rnk-t[p<<1]); } int main(){ scanf("%d%d%d",&n,&m,&Q); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); a[x].first++; } for(int i=1;i<=m;i++)a[i].second=i; sort(a+1,a+m+1); for(int i=1;i<=Q;i++)scanf("%lld",&q[i].first),q[i].second=i; sort(q+1,q+Q+1); int l,r,pos; long long now=n,nxt; for(l=1,r=1,pos=1;;l=r){ for(;r<=m&&a[r].first==a[l].first;r++)change(1,1,m,a[r].second); if(r>m)break; nxt=now+(long long)(a[r].first-a[l].first)*(r-1); for(;pos<=Q&&q[pos].first<=nxt;pos++){ ans[q[pos].second]=kth(1,1,m,mod(q[pos].first-now,r-1)); } now=nxt; } for(;pos<=Q;pos++){ ans[q[pos].second]=mod(q[pos].first-now,m); } for(int i=1;i<=Q;i++)printf("%dn",ans[i]); return 0; }
转载于:https://www.cnblogs.com/BlogOfchc1234567890/p/11051532.html
最后
以上就是甜美外套最近收集整理的关于Codeforces 11811181 B1181 C1181 D的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复