题目链接：http://codeforces.com/contest/818/problem/A
A：数学，水题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL n, k;
scanf("%lld%lld",&n,&k);
LL x = n/(2*(k+1));
if(x == 0){
printf("0 0 %lld\n", n);
}
else{
printf("%lld %lld %lld\n", x, k*x, n-(k+1)*x);
}
}B，水题，模拟。题意：给出一个排列a1…an，进行m轮游戏，首先选定一个leader作为l[1]，l[i+1]=a[l[i]]+l[i] a[l[i]]+l[i]=l[i+1] 所以 a[l[i]]=l[i+1]-l[i] 如果遇到有冲突的情况特判一下输出-1（一个以上的位置是同一个数或同一个位置几次得到的结果不一样）
#include <bits/stdc++.h>
using namespace std;
int n, m, l[110], a[110], ans[110], temp[110];
int vis[110];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) scanf("%d",&l[i]);
bool flag = 0;
for(int i=1; i<=n; i++){
int st = l[1];
memset(vis, 0, sizeof(vis));
memset(temp, 0, sizeof(temp));
int pos = 1;
temp[1] = i;
vis[i] = 1;
bool ok = 1;
for(int j=2; j<=m; j++){
if(temp[st]==0){
int x = l[j]-l[j-1];
if(x<=0) x+=n;
if(x>n) x-=n;
temp[st]=x;
++vis[x];
st = l[j];
}
else{
int x = temp[st]+st;
if(x>n) x-=n;
if(x==l[j]){
st = l[j];
}
else{
ok = 0;
}
}
}
for(int j=1; j<=n; j++){
if(vis[j]>1){
ok = 0;
break;
}
}
if(ok){
for(int j=1; j<=n; j++){
if(temp[j]) ans[j] = temp[j];
else{
for(int k=1; k<=n; k++){
if(!vis[k]){
ans[j] = k;
vis[k] = 1;
break;
}
}
}
}
flag = 1;
break;
}
}
if(flag==0){
puts("-1");
}
else{
for(int i=1; i<=n; i++) printf("%d ", ans[i]);
printf("\n");
}
return 0;
}C：有d个沙发，每个沙发占据相邻两个格子，定义一个沙发A在另一个沙发B左边为：存在沙发A的格子a和沙发B的格子b使得xa小于xb，求出一个沙发满足给出的cntl,cntr,cntt,cntb m和n都不超过1e5，直接处理出前缀和，O(n)可求
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct node{
int x1,y1,x2,y2;
}sofa[maxn];
int d, n, m, cntl, cntr, cntt, cntb, ans, sum1[maxn], sum2[maxn], sum3[maxn], sum4[maxn];
int main(){
scanf("%d%d%d", &d,&n,&m);
for(int i=1; i<=d; i++){
scanf("%d%d%d%d", &sofa[i].x1,&sofa[i].y1,&sofa[i].x2,&sofa[i].y2);
sum1[min(sofa[i].x1,sofa[i].x2)]++;
sum2[max(sofa[i].x1,sofa[i].x2)]++;
sum3[min(sofa[i].y1,sofa[i].y2)]++;
sum4[max(sofa[i].y1,sofa[i].y2)]++;
}
scanf("%d%d%d%d", &cntl,&cntr,&cntt,&cntb);
for(int i=1; i<=n; i++) sum1[i]+=sum1[i-1];
for(int i=n; i>=1; i--) sum2[i]+=sum2[i+1];
for(int i=1; i<=m; i++) sum3[i]+=sum3[i-1];
for(int i=m; i>=1; i--) sum4[i]+=sum4[i+1];
ans = -1;
for(int i=1; i<=d; i++){
int l = sum1[max(sofa[i].x1, sofa[i].x2)-1];
int r = sum2[min(sofa[i].x1, sofa[i].x2)+1];
if(sofa[i].x1 != sofa[i].x2) l--, r--;
int t = sum3[max(sofa[i].y1, sofa[i].y2)-1];
int b = sum4[min(sofa[i].y1, sofa[i].y2)+1];
if(sofa[i].y1 != sofa[i].y2) t--,b--;
if(l == cntl && r == cntr && t == cntt && b == cntb){
ans = i;
break;
}
}
printf("%d\n", ans);
return 0;
}
D,有n辆车依次驶过，给定对方选择的一个颜色a，请你选择一个颜***使得在任一时刻cntb>=cnta。
解法：这道题本来O(n)扫一遍就好了，***强行怼了线段树。我的做法就是对所有的颜色开一个线段树，当颜色等于A的时候所有颜色的值-1，不等于A的时候，如果当前颜色所在位置的值>=0的话，给当前值+1，最后查找这个线段树有没有>=0的节点，有的话输出这个值就好了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int n, A, c[maxn];
struct node{
int l,r,len,sum;
int lazy;
}tree[maxn*4];
void pushup(int rt){
tree[rt].sum = tree[rt*2].sum+tree[rt*2+1].sum;
}
void pushdown(int rt){
if(tree[rt].lazy){
tree[rt*2].lazy+=tree[rt].lazy;
tree[rt*2+1].lazy+=tree[rt].lazy;
tree[rt*2].sum += tree[rt*2].len*tree[rt].lazy;
tree[rt*2+1].sum += tree[rt*2+1].len*tree[rt].lazy;
tree[rt].lazy = 0;
}
}
void Build(int l, int r, int rt){
tree[rt].l = l, tree[rt].r = r, tree[rt].sum = 0, tree[rt].lazy = 0, tree[rt].len = r-l+1;
if(l == r){
return;
}
int mid = (l+r)/2;
Build(l,mid,rt*2);
Build(mid+1,r,rt*2+1);
pushup(rt);
}
void update(int L, int R, int c, int rt){
if(L<=tree[rt].l&&tree[rt].r<=R){
tree[rt].sum += c*(tree[rt].len);
tree[rt].lazy += c;
return;
}
pushdown(rt);
int mid = (tree[rt].l+tree[rt].r)/2;
if(R<=mid) update(L,R,c,rt*2);
else if(L>mid) update(L,R,c,rt*2+1);
else{
update(L,mid,c,rt*2);
update(mid+1,R,c,rt*2+1);
}
pushup(rt);
}
int query(int L, int R, int rt){
if(L<=tree[rt].l&&tree[rt].r<=R){
return tree[rt].sum;
}
pushdown(rt);
int mid = (tree[rt].l+tree[rt].r)/2;
if(R<=mid) return query(L,R,rt*2);
else if(L>mid) return query(L,R,rt*2+1);
else return query(L,mid,rt*2)+query(mid+1,R,rt*2+1);
}
int main()
{
scanf("%d%d",&n,&A);
for(int i=1; i<=n; i++) scanf("%d", &c[i]);
Build(1,1000000,1);
int ans = -1;
for(int i=1; i<=n; i++){
if(c[i]==A){
update(1,1000000,-1,1);
}
else{
if(query(c[i],c[i],1)>=0){
update(c[i],c[i],1,1);
}
}
}
for(int i=1; i<=1000000; i++){
if(i==A) continue;
if(query(i,i,1)>=0){
ans = i;
break;
}
}
printf("%d\n", ans);
return 0;
}E，有多少连续的ai…aj的乘积是k的倍数
解法：将k分解质因数，处理出序列每个质因数个数的前缀和，对于每个左端点通过二分来得到最小的能使乘积为k的倍数的右端点
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 400010;
LL n, k;
LL a[maxn];
LL num1[20], num2[20], cnt=0;
LL sum[maxn][20];
bool check(LL x, LL y){
for(int i=0; i<cnt; i++){
LL temp = sum[y][i]-sum[x-1][i];
if(temp<num2[i]) return false;
}
return true;
}
int main()
{
scanf("%lld%lld", &n,&k);
LL x = k;
for(LL i=2; i*i<=x; i++){
if(x%i==0){
int p = 0;
num1[cnt++] = i;
while(x%i==0){
x/=i;
p++;
}
num2[cnt-1] = p;
}
}
if(x > 1){
num1[cnt++] = x;
num2[cnt-1] = 1;
}
memset(sum, 0, sizeof(sum));
for(LL i=1; i<=n; i++){
scanf("%lld", &a[i]);
for(int k = 0; k < cnt; k++){
sum[i][k] = sum[i-1][k];
while(a[i]%num1[k]==0){
sum[i][k]++;
a[i]/=num1[k];
}
}
}
LL anss = 0;
for(LL i=1; i<=n; i++){
LL l = i, r = n, ans = n;
while(l<=r){
LL mid = (l+r)/2;
if(check(i, mid)) ans = mid, r=mid-1;
else l = mid+1;
}
if(check(i, ans)) anss = anss+n-ans+1;
}
printf("%lld\n", anss);
return 0;
}F，n个点的图，桥的个数要求不小于边数的一半，问边数的最大值
解法：n个点中k个点两两相连有k*(k-1)/2条边，其余的点顺次相连为桥n-k条边，当k*(k-1)/2<=n-k时才符合要求 可以发现f(k)=n-k+min(n-k,k*(k-1)/2)是一个单峰函数，于是三分得到答案
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int q;
LL n, ans;
LL check(LL mid){
return n-mid+min(n-mid,(mid-1)*mid/2);
}
int main(){
scanf("%d", &q);
while(q--){
scanf("%lld", &n);
LL l = 1, r = n;
while(l + 1 < r){
LL mid = (l+r)/2;
LL midd = (mid+r)/2;
if(check(mid)<check(midd)) l = mid;
else r = midd;
}
printf("%lld\n", max(check(l),check(l+1)));
}
}G,没读
京公网安备 11010502036488号