Programiranje 方法记录

[COCI2017-2018#3] Programiranje题面翻译题目描述Little Leticija正在准备编程考试 。虽然她已经解决了很多任务,但还有一个任务尚未解决,所以她正在向你寻求帮助 。您将获得单词S和Q查询 。在每个查询中,给出正整数A,B,C和D.假设单词X由单词S中位置A和B之间的字母组成,而单词S中位置C和D之间的字母组成单词Y.如果可以以某种方式重新排列单词Y中的字母并获得单词X,则必须回答 。
输入输出格式** 输入格式:**第一行输入包含单词S(1≤| S |≤50000) 。| S | 表示单词S中的字符数,由英文字母的小写字母组成 。第二行输入包含正整数Q(1≤Q≤50000) 。以下Q行中的每一行包含来自任务的四个整数A,B,C i D(1≤A≤B≤| S |且1≤C≤D≤| S |) 。** 输出格式:**对于每个查询,如果可能,输出“DA”(克罗地亚语为yes),如果不可能,则输出“NE”(克罗地亚语为否) 。
输入输出样例**输入样例#1: **
kileanimal22 2 7 71 4 6 7**输出样例#1: **
DANE输入样例#2:
abababba23 5 1 31 2 7 8**输出样例#2: **
DADA输入样例#3:
vodevovode25 8 3 62 5 3 6**输出样例#3: **
【Programiranje 方法记录】NEDA说明在总分为50%的测试用例中,它将保持:1≤| S | ≤1000且1≤Q≤1000 。澄清第三个测试用例:在第一个查询中,X =“vovo”,Y =“devo” 。在第二个查询中,X =“odev” , Y =“devo” 。
题目描述Little Leticija is preparing for a programming exam. Even though she has solved a lot of tasks, there’s one still left unsolved, so she is asking you for help. You are given the word S and Q queries. In each query, you are given positive integers A, B, C and D. Let’s say that word X consists of letters between positions A and B in word S, and word Y from letters between positions C and D in word S. For each query, you must answer if it is possible to somehow rearrange the letters in word Y and obtain word X.
输入格式The first line of input contains the word S (1 ≤ |S| ≤ 50 000). |S| denotes the number of characters in word S, which consists of lowercase letters of the English alphabet. The second line of input contains the positive integer Q (1 ≤ Q ≤ 50 000).
Each of the following Q lines contains four integers A, B, C i D (1 ≤ A ≤ B ≤ |S| and 1 ≤ C ≤ D ≤ |S| ) from the task.
输出格式For each query, output “DA” (Croatian for yes) if it is possible, and “NE” (Croatian for no) if it is not.
样例 #1样例输入 #1kileanimal22 2 7 71 4 6 7样例输出 #1DANE样例 #2样例输入 #2abababba23 5 1 31 2 7 8样例输出 #2DADA样例 #3样例输入 #3vodevovode25 8 3 62 5 3 6样例输出 #3NEDA提示In test cases worth 50% of total points, it will hold: 1 ≤ |S| ≤ 1000 and 1 ≤ Q ≤ 1000.
Clarification? ?of? ?the? ?third? ?test? ?case:
In the first query, X=”vovo”, and Y=”devo”. In the second query, X=”odev”, and Y=”devo”.
审题题意转化:“单词\(X\)能以某种方式重新排列得到单词\(Y\)”,其实就是两个单词中的元素相同,即每种字母出现的次数分别相同 。又一看询问,“区间查询”,于是我们想到用统计每一个字母出现次数的前缀和 , 再用前缀和离线地比较每种字母出现的次数 。
具体地,我们用二维数组\(pre[i][j]\)来记录从第\(1\)位到第\(i\)位,字母\(j\)出现的次数 。(方便起见 , 直接用字母的\(ascii\)码值表示字母)
比如 , \(pre[5][97]=2\)就是指从第\(1\)位到第\(5\)位,字母\(a\)出现了两次 。
从而,对于每一个询问,我们只需要比较每种字母出现次数是否相等即可 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=50005;int pre[N][30];char s[N];int q,len;int main(){ scanf("%s",s+1); len=strlen(s+1); for(int i=1;i<=len;i++) {for(int j=1;j<=26;j++) pre[i][j]+=pre[i-1][j];//分别记录每种字母出现次数的前缀和pre[i][s[i]-'a'+1]++;//当前位对应字母累加 } scanf("%d",&q); while(q--) {int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);if(b-a!=d-c)//如果两个单词的长度不相等 , 就肯定NE{puts("NE");continue;}bool flag=1;for(int i=1;i<=26;i++){int tmp1=pre[b][i]-pre[a-1][i];//a~b第i个字母出现次数int tmp2=pre[d][i]-pre[c-1][i];//c~d第i个字母出现次数if(tmp1!=tmp2)//若某个字母出现次数不相等,则直接判NE{flag=0;break;}}if(flag) puts("DA");else puts("NE"); } return 0;}

    推荐阅读