题目链接:Codeforces 390C Inna and Candy Boxes
题目大意:给出n,k和w,然后给出n个礼物盒的状况,‘1’表示有糖果,‘0’表示没有糖果,然后给出w次询问,每次询问将[l,r]区间变成标准情况需要几步,标准情况为l-1+k,l-1+2k....的盒子有糖果,其他在该区间上的盒子没有糖果。
解题思路:因为k不会大于10,所以可以先进行预先处理,将以0~k为起始的位置进行处理,dp[i][j]表示说以i为开头,区间[1,j]需要几步。然后特殊处理一下左区间的边界。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 100005;
int n, k, w, s[15][N];
char str[N];
bool judge(int x, int y) {
if ((y - x + k + 1) % k == 0 && str[y-1] == '0') return true;
if ((y - x + k + 1) % k != 0 && str[y-1] == '1') return true;
return false;
}
void init () {
memset(s, 0, sizeof(s));
scanf("%d%d%d%s", &n, &k, &w, str);
int len = strlen(str);
for (int i = 0; i < k; i++) {
for (int j = i+1; j <= len; j++) {
s[i][j] = s[i][j-1];
if (judge(i, j)) s[i][j]++;
}
}
}
int handle(int x) {
if (k == 1) {
if (str[x-1] == '0') return 1;
} else {
if (str[x-1] == '1') return 1;
}
return 0;
}
void solve () {
int x, y;
for (int i = 0; i < w; i++) {
scanf("%d%d", &x, &y);
int t = x % k;
printf("%d\n", s[t][y] - s[t][x] + handle(x));
}
}
int main () {
init ();
solve();
return 0;
}
分享到:
相关推荐
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
Codeforces round 678 D2_Codeforces_源码
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
打codeforces的神器
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces-js Codeforces JS
Codeforces Round #723 (Div. 2).md
PDF-CodeForces问题 PDF文件中的CodeForces问题 利用CodeForces提取在这个库中的文件 ,文件夹名代表来自CodeForces网址contests`的ID,每个文件夹包含比赛的问题。 有关CodeForces竞赛的疯狂事实 CodeForces上有937...