64-bit integer IO format: %lld      Java class name: Main

Next

None
 
Graph Theory
 
    2-SAT
 
    Articulation/Bridge/Biconnected Component
 
    Cycles/Topological Sorting/Strongly Connected Component
 
    Shortest Path
 
        Bellman Ford
 
        Dijkstra/Floyd Warshall
 
    Euler Trail/Circuit
 
    Heavy-Light Decomposition
 
    Minimum Spanning Tree
 
    Stable Marriage Problem
 
    Trees
 
    Directed Minimum Spanning Tree
 
    Flow/Matching
 
        Graph Matching
 
            Bipartite Matching
 
            Hopcroft–Karp Bipartite Matching
 
            Weighted Bipartite Matching/Hungarian Algorithm
 
        Flow
 
            Max Flow/Min Cut
 
            Min Cost Max Flow
 
DFS-like
 
    Backtracking with Pruning/Branch and Bound
 
    Basic Recursion
 
    IDA* Search
 
    Parsing/Grammar
 
    Breadth First Search/Depth First Search
 
    Advanced Search Techniques
 
        Binary Search/Bisection
 
        Ternary Search
 
Geometry
 
    Basic Geometry
 
    Computational Geometry
 
    Convex Hull
 
    Pick's Theorem
 
Game Theory
 
    Green Hackenbush/Colon Principle/Fusion Principle
 
    Nim
 
    Sprague-Grundy Number
 
Matrix
 
    Gaussian Elimination
 
    Matrix Exponentiation
 
Data Structures
 
    Basic Data Structures
 
    Binary Indexed Tree
 
    Binary Search Tree
 
    Hashing
 
    Orthogonal Range Search
 
    Range Minimum Query/Lowest Common Ancestor
 
    Segment Tree/Interval Tree
 
    Trie Tree
 
    Sorting
 
    Disjoint Set
 
String
 
    Aho Corasick
 
    Knuth-Morris-Pratt
 
    Suffix Array/Suffix Tree
 
Math
 
    Basic Math
 
    Big Integer Arithmetic
 
    Number Theory
 
        Chinese Remainder Theorem
 
        Extended Euclid
 
        Inclusion/Exclusion
 
        Modular Arithmetic
 
    Combinatorics
 
        Group Theory/Burnside's lemma
 
        Counting
 
    Probability/Expected Value
 
Others
 
    Tricky
 
    Hardest
 
    Unusual
 
    Brute Force
 
    Implementation
 
    Constructive Algorithms
 
    Two Pointer
 
    Bitmask
 
    Beginner
 
    Discrete Logarithm/Shank's Baby-step Giant-step Algorithm
 
    Greedy
 
    Divide and Conquer
 
Dynamic Programming
                  Tag it!

为了准备GRE考试，大玉儿每天都要背单词。新东方的老师说，背单词就是不断地重复，于是他制定了一项计划，第一天初次记忆之后，在以后的某些天（比如第二天，第四天，第七天，第十五天，第三十天）再把这些单词看一遍。他发现这个方法效果很好，但是每个月总有那么几天，他需要看非常非常多的单词。于是，他想写个程序来知道某一天需要看多少个单词。

大玉儿一共要背D天的新单词（即没有复习的情况下，要连续背D天），每天背的新单词个数是N1,N2,…ND。他又制定了K个复习点，R1,R2,…,RK，表示在背完某天单词的第R1天，第R2天，……，第RK天，他会把那天的单词再复习一遍（所有D天的新单词都会按照这个计划复习）。Ri=1，则说明背单词当天就复习一遍，Ri=2表示背新单词的后一天会复习一遍。

接下来，大玉儿会有M个询问，Q1,Q2,…,QM，第i个询问表示大玉儿想知道第Qi天会看多少个单词（包括当天要记的新单词）。

测试数据有多组，第一行是一个整数T（0<T<=30），表示数据组数。

对于每一组数据，第一行是一个正整数D(1<=D<=100)，接下来一行有D个整数N1 N2 … ND，每个数之间用空格隔开，Ni表示大钰儿在第i天要看的新单词的数量(1<=Ni<=2000)。第三行有一个正整数K(1<=K<=100)，表示有K个复习点。第四行有K个整数R1 R2 … RK，表示这K个复习点的时间（保证R1<R2<…<RK，且1<=Ri<=2000）。第五行是一个正整数M，表示有M个询问(1<=M<=10000)。第六行有M个整数Q1 Q2 … QM(1<=Qi<=10000)，表示大钰儿想知道第Qi天要看多少个单词（从开始背新单词的那天算作第一天）。

对于每组数据，对每个询问输出一行，第i行表示第Qi天大钰儿要看的单词数。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int N[110];

        int R[110];

        int ans[11000];

        int D;

        memset(ans,0,sizeof(ans));

        scanf("%d",&D);

        for(int i=1;i<=D;i++){

            scanf("%d",&N[i]);

            ans[i]=N[i];

        }

        int K;

        scanf("%d",&K);

        for(int i=1;i<=K;i++){

            scanf("%d",&R[i]);

        }

        for(int i=1;i<=D;i++){

            for(int j=1;j<=K;j++){

               ans[i+R[j]-1]+=N[i];

            }

        }

        int M;

        scanf("%d",&M);

        for(int i=1;i<=M;i++){

            int tmp;

            scanf("%d",&tmp);

            printf("%d\n",ans[tmp]);

        }

    }

    return 0;

}