2 seconds
256 megabytes
standard input
standard output
Genos needs your help. He was asked to solve the following programming problem by Saitama:
The length of some string s is denoted |s|. The Hamming distance between two strings s and t of equal length is defined as 
, where si is the i-th character of s and ti is the i-th character of t. For example, the Hamming distance between string "0011" and string "0110" is |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2.
Given two binary strings a and b, find the sum of the Hamming distances between a and all contiguous substrings of b of length |a|.
The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000).
The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000).
Both strings are guaranteed to consist of characters '0' and '1' only.
Print a single integer — the sum of Hamming distances between a and all contiguous substrings of b of length |a|.
01
00111
3
0011
0110
2
For the first sample case, there are four contiguous substrings of b of length |a|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.
The second sample case is described in the statement.
题意：给你两个01串s，t ; 在t中取连续的长度为|s|的部分 求和输出
题解：对于s串中的每一个位置i的数都与t串中[i,lent-(lens-i)]计算一次，记录t串中的1的前缀乱搞。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
char a[];
char b[];
int sum1[];
int sum0[];
int main()
{
scanf("%s",a+);
scanf("%s",b+);
int len1=strlen(b+);
int len2=strlen(a+);
sum0[]=;
sum1[]=;
for(int i=;i<=len1;i++)
{
sum1[i]=sum1[i-];
sum0[i]=sum0[i-];
if(b[i]=='')
sum1[i]++;
else
sum0[i]++;
}
ll ans=;
for(int i=;i<=len2;i++){
if(a[i]=='')
ans=ans+sum1[len1-(len2-i)]-sum1[i-];
else
ans=ans+sum0[len1-(len2-i)]-sum0[i-];
}
printf("%I64d\n",ans);
return ;
}
2 seconds
256 megabytes
standard input
standard output
There are n beacons located at distinct positions on a number line. The i-th beacon has position ai and power level bi. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance bi inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.
Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos's placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.
The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the initial number of beacons.
The i-th of next n lines contains two integers ai and bi (0 ≤ ai ≤ 1 000 000, 1 ≤ bi ≤ 1 000 000) — the position and power level of the i-th beacon respectively. No two beacons will have the same position, so ai ≠ aj if i ≠ j.
Print a single integer — the minimum number of beacons that could be destroyed if exactly one beacon is added.
4
1 9
3 1
6 1
7 4
1
7
1 1
2 1
3 1
4 1
5 1
6 1
7 1
3
For the first sample case, the minimum number of beacons destroyed is 1. One way to achieve this is to place a beacon at position 9 with power level 2.
For the second sample case, the minimum number of beacons destroyed is 3. One way to achieve this is to place a beacon at position 1337 with power level 42.
题意：给你n个灯塔的位置与高度 现在 在最右边增加一个灯塔 输出最少能覆盖的灯塔的个数
题解：dp[i] 表示以第i个灯塔为（最右边一个没有被覆盖的灯塔）的左边的灯塔覆盖个数
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
int n;
int mp[];
int dp[];
int sum[];
int a,b;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d %d",&a,&b);
mp[a]=b;
}
if(mp[]==){
sum[]=;
dp[]=;
}
else
{
sum[]=;
dp[]=;
}
int ans=1e9;;
for(int i=;i<=;i++){
sum[i]=sum[i-];
if(mp[i]!=)
sum[i]++;
}
for(int i=;i<=;i++)
{
if(mp[i]==)
dp[i]=dp[i-];
else
{
int now=max(,i-mp[i]);
if(now==)
dp[i]=sum[i-];
else
dp[i]=dp[now-]+(sum[i-]-sum[now-]);
}
ans=min(ans,dp[i]+sum[]-sum[i]);
}
printf("%d\n",ans);
return ;
}
2 seconds
512 megabytes
standard input
standard output
Genos recently installed the game Zuma on his phone. In Zuma there exists a line of n gemstones, the i-th of which has color ci. The goal of the game is to destroy all the gemstones in the line as quickly as possible.
In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?
Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.
The first line of input contains a single integer n (1 ≤ n ≤ 500) — the number of gemstones.
The second line contains n space-separated integers, the i-th of which is ci (1 ≤ ci ≤ n) — the color of the i-th gemstone in a line.
Print a single integer — the minimum number of seconds needed to destroy the entire line.
3
1 2 1
1
3
1 2 3
3
7
1 4 4 2 3 2 1
2
In the first sample, Genos can destroy the entire line in one second.
In the second sample, Genos can only destroy one gemstone at a time, so destroying three gemstones takes three seconds.
In the third sample, to achieve the optimal time of two seconds, destroy palindrome 4 4 first and then destroy palindrome 1 2 3 2 1.
题意：消除回文 问最少几次消除全部
题解：简单区间dp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
int n;
int a[];
int dp[][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
dp[i][j]=1e9;
for(int i=;i<=n;i++)
dp[i][i]=;
for(int i=n;i>=;i--)
{
for(int j=i+;j<=n;j++)
{
for(int k=i;k<=j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
if(a[i]==a[j]){
if(i+==j)
dp[i][j]=;
else
dp[i][j]=min(dp[i][j],dp[i+][j-]);
}
}
}
printf("%d\n",dp[][n]);
return ;
}