A题 第K小的和

Tom有n个数字Ai，每个数字都不⼀一样。现在，Tom想把这些数字次数的选择，然后 把选定的数字求和，例如： Tom有2个数字，这2个数字分别是：3，5，那么，他能够组成的数字有： 3，5，6，8，9，10，11，12… 现在，他好奇组成的和中，第k⼩小的是多少，你能告诉他么？

输⼊入格式： 第⼀一⾏行两个正整数n，k表⽰示Tom⼿手上数字的个数，以及要求的是第⼏几⼩小的数字。 第⼆二⾏行n个正整数Ai，表⽰示Tom⼿手上每个数字的值。

输出格式： ⼀一个正整数，表⽰示第k⼩小的数是多少。

输⼊入/输出样例：

kth.in：

2 8

3 5

kth.out： 8

30%数据：保证ans<=100,000

60%数据：k<=100,000

100%数据:k<=100,000,000

100%数据：n<=100,每个数字<=1000，答案在64位整数范围内且gcd(Ai)=1。

思考：

看到GCD（Ai)=1 我就开始猜这是一道数学题目了，在我的无限乱搞之下发现数字必定会在某个点之后连续即从n点之后到之后任意一个数都可以到达。

但是这个n点非常难找，我继续猜我的瞎结论 n点必定于最小的两个Ai有关 在搞了几组数据看了之后发现，的确如此，n点在Ai*Ai+1*gcd(Ai,Ai+1)之前 Ai和Ai+1表示最小的两个数

怎么证明呢？（抱歉我不会，我只是和暴力程序对拍了100多组数据。）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define go(i,a,b) for(register int i =a;i<=b;i++)#define ro(i,a,b) for(register int i =a;i>=b;i--)using namespace std;#define LL long long int n;LL a[105];priority_queue
          
           
            ,greater
            
              > q;LL k;bool book[100000005];int main(){ freopen("kth.in","r",stdin); freopen("kth.out","w",stdout); cin>>n>>k; int minn,subn; int flag=0; int num=0; go(i,1,n) { cin>>a[i]; if(book[a[i]]==0) { q.push(a[i]);book[a[i]]=1;num++; } if(a[i]==1) flag=1; } LL tt=0; if(flag==1) { cout<
             
              <
              
               =chen) { duandian=now; break; } go(i,1,n) { LL p=now+a[i]; if(book[p]==0) { q.push(p);book[p]=1; } } q.pop(); } LL ans=duandian+(k-tt); if(k!=tt+1) cout<
               
                <
               
              
             
            
           
          
         
        
       
      
     

 

 

B题 消砖块

游戏画⾯面是由⼀一个N*M的砖块矩阵构成的，每个砖块有⼀一种颜⾊色。两个砖块相邻当 且仅当他们在上、下、左、右四个⽅方向上相邻。⽩白⾊色砖块是游戏中特有的砖块，可以当 做任何⼀一个颜⾊色。 游戏的过程是这样的：点击任何⼀一个有砖块的位置，如果该砖块与其他和它颜⾊色相 同的砖块构成的连通块中，砖块的个数⼤大于等于1个，则将这些砖块全部消掉，消掉后， 上⽅方的砖块⾸首先下落，下落后整列向左平移直到所有空⽩白列都在右边为⽌止。

以下是⼀一个掉落的情况，消除颜⾊色2，⾸首先其他砖块掉落，然后平移：

1 1 2 3             ——》    1 0 0 0             ——》    1 0 0 0

1 2 2 3             ——》    1 0 0 3             ——》    1 0 3 0

1 2 2 2             ——》    1 1 0 3             ——》    1 1 3 0

我们的问题很简单：对于⼀一个给定的游戏局⾯面，最少需要消除⼏几次能够使所有砖块 都消完呢？（数据中没有⽩白⾊色砖块）

输⼊入格式： 第⼀一⾏行两个整数n,m，表⽰示矩阵的尺⼨寸。 之后n⾏行m列，表⽰示每个位置的颜⾊色。 输出格式： ⼀一个整数，表⽰示最少的消除次数，题⺫⽬目保证有解。

输⼊入/输出样例： game.in： 3 3

2 2 3

2 1 3 

3 1 1

kth.out： 3

解释： 先消除2，再消除1，再消除3，则全部消完。

30%数据：1<=n,m<=5

60%数据：1<=n,m<=7

100%数据: 1<=n,m<=8

100%数据：1<=颜⾊色<=n*m，保证初始每个格⼦子都>0，且最多有5种不同的颜⾊色。

 

IDA算法 待补~

 

 

T3 李世乭的单词表

李世乭很喜欢背单词，且对⾃自⼰己的记忆⼒力很有信⼼心，某天，他背了p开头的⼀一些单词

：

prada,pre,prepare,preview… 并放出豪⾔言：这些单词我记得滚⽠瓜烂熟，甚⾄至可以倒背如流。 这可让来⾃自美国的Alpha-Go不满了，Alpha-Go说：我提问你⼀一系列问题，每个问 题问你：从你背的第L个单词到第R个单词中，有多少个以前缀X开头的单词，你能做到 么？例如，L=2，R=4，X=“pre”，答案是3。 李世乭很快被问倒了，他表⽰示，世界上除了来⾃自中国的Anima-Out，没⼈人能搞的 定，⾝身为Anima-Out的发明者你能够帮他解决这个问题么？

输入格式：

第一⾏行两个正整数n，q，表⽰示李世乭背了n个单词，Alpha-Go做了q次提问。 之后n⾏行，每⾏行⼀一个单词。 之后q⾏行，每⾏行L，R，X，表⽰示询问的区间以及前缀X。

注意：单词并不是⼀一定按照字典序。

输出格式：

q⾏行，每⾏行⼀一个整数，表⽰示对应问题的答案。

输⼊入/输出样例：

dict.in：

4 2

prada

prepare

pre

preview

1 3 pre

1 4 pr

kth.out： 2 4

30%数据：n<=1000,q<=1000 100%数据：n<=100000,q<=100000 100%数据：每个单词长度<=20且都是⼩小写字母。

字典树+前缀和,ORZ

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;int n,q;struct ve{ int flag,id; string word;};struct node{ int num; int son[27]; }trie[100000*20];vector
            
             now[100005];string word[100005];int ask[100005],tot,x,y;void Start(string word){ int now = 0; for(int i = 0;i
             
              >n>>q; for(int i=1;i<=n;i++){ cin>>word[i]; } for(int i=1;i<=n;i++) now[i].clear(); memset(ask,0,sizeof(ask)); memset(trie,0,sizeof(trie)); string fuck; ve sb; for(int i=1;i<=q;i++){ cin>>x>>y>>fuck; sb.flag=-1; sb.id=i; sb.word=fuck; now[x-1].push_back(sb); sb.flag=1; now[y].push_back(sb); } for(int i=1;i<=n;i++){ Start(word[i]); for(int j=0;j