EOJ Monthly 2017.12 (暨 ECNU 12 月内部選拔) 題解

比賽連結

題解連結

A 水題，模拟即可

B. 在哈爾濱的寒風中

Time limit per test: 1.0 seconds

Memory limit: 256 megabytes

kblack 來到了寒冬中的哈爾濱，哈爾濱的寒風令 kblack 瑟瑟發抖。

世界上最遠的距離，是你與飯店隻差一條冰街，而你卻忘了穿上秋褲。

kblack 終于沖進了飯店，飯店大廳的地闆鋪滿了五顔六色的地磚，可以被看作是一塊 n×m 格的棋盤，為了能使凍僵了的雙腳盡快暖和起來，kblack 決定在地磚上走動，但是他被速凍的雙腳在棋盤地闆上隻能走馬步。

kblack 居然想知道有多少對地磚（無序點對）他可以通過若幹步馬步互相抵達！

Input

輸入包含一行兩個正整數 n, m，表示棋盤的大小，保證 1≤n×m≤109 。

Output

輸出包含一個整數，表示 kblack 可以通過馬步互相到達的無序地磚對數。

Examples

input

1 2

output

input

4 2

output

思路：

第2次嘗試用大數，比賽時候沒有發現n*m<=1e9,最後其實不用大數也能過，

雖然限制隻能走馬步，但我們很容易意識到在足夠大的棋盤（例如象棋棋盤）上，馬可以達到任何位置。事實上通過簡單的驗證，可以發現這一大小的下界是 3×4。

于是對于所有 ≥3×4 的棋盤，我們可以斷言所有磚之間可以互相到達，此時答案為 (nm2)。

當棋盤大小為 3×3 時，通過簡單的模拟可以發現外圍的 8 塊磚可以互相到達，此時答案為 (82)。

當棋盤大小為 2×n 時，我們發現不同奇偶不同的行/列交替可達，此時有 2 組 ⌊n/2⌋ 的聯通塊與兩組 n−⌊n/2⌋ 的聯通塊，答案為 2×(⌊n/2⌋2)+2×(n−⌊n/2⌋2)。

當棋盤大小為 1×n 時，沒有合法的馬步，此時答案為 0。

注意答案可能超過 2147483647，需要使用 long long 類型。

c++

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    if (n ==  || m == ) printf("0\n");
    else if (n ==  || m == ){
        n = max(n, m);
        printf("%lld\n", (n/)*(n/-)+(n-n/)*(n-n/-));
    }
    else if (n ==  && m == ) printf("28\n");
    else printf("%lld\n", n*m*(n*m-)/);
    return ;
}

java

import java.math.BigInteger;
import java.util.*;

public class Main {
    private static Scanner scan;

    public static void main(String[] args) {
        scan = new Scanner(System.in 

);
            BigInteger n,m,u1,u2,u3;
                n=scan.nextBigInteger();
                m=scan.nextBigInteger();
            BigInteger t1 = BigInteger.valueOf();
            BigInteger t2 = BigInteger.valueOf();
            BigInteger t3 = BigInteger.valueOf();
        //  System.out.println(n);
            if(n.equals(t1)||m.equals(t1))
                System.out.println("0");
            else if(n.equals(t3)&&m.equals(t3))
                System.out.println("28");
            else if(n.equals(t2))
            {
                u1 = m.subtract(t1);
                u2 = m.subtract(t2);
                u1 = u1.multiply(u2);
                u1 = u1.divide(t2);
                 u3 = m.subtract(t3);
                 u3 = u3.add(t2);
                 u3 = u3.divide(t2);
                 u3 = u3.add(u1);
                 System.out.println(u3);
            }

            else if(m.equals(t2))
            {
                u1 = n.subtract(t1);
                u2 = n.subtract(t2);
                u1 = u1.multiply(u2);
                u1 = u1.divide(t2);
                 u3 = n.subtract(t3);
                 u3 = u3.add(t2);
                 u3 = u3.divide(t2);
                 u3 = u3.add(u1);
                 System.out.println(u3);
            }

            else
            {
                n  = n.multiply(m);
                //System.out.println(n);
                m = n;
                //System.out.println(m);
                m = m.subtract(t1);
                //System.out.println(m);

                //System.out.println(m);
                n = n.multiply(m);
                n = n.divide(t2);
                System.out.println(n);
            }             
    }
}

G1. 唐納德與子串 (Easy)

Time limit per test: 1.0 seconds

Memory limit: 256 megabytes

子串的定義是在一個字元串中連續出現的一段字元。這裡，我們使用 s[l…r] 來表示 s 字元串從 l 到 r（閉區間）的子串。在本題中，字元串下标從 0 開始。顯然，對于長度為 n 的字元串共有 n(n+1)2 個子串。

對于一個給定的字元串 s，唐納德給出 q 次詢問，第 i 次詢問包括三個參數 li,ri,zi，問在 s[li…ri] 的所有子串中共有多少個恰好為 zi。

Input

輸入具有如下形式：

sql1 r1 z1l2 r2 z2⋮lq rq zq

第一行一個字元串 s。

第二行一個整數 q。

接下來每行：首先兩個整數 li,ri (0≤li≤ri<|s|)，然後是一個非空字元串 zi。整數和整數，整數和字元串間以單空格隔開。

字元串中隻會出現 26 個小寫英文字母。

資料規模約定：

對于 Easy 檔：1≤|s|≤100,q≤∑|zi|≤100。

對于 Hard 檔：1≤|s|≤105,q≤∑|zi|≤105。

Output

對于每次詢問，輸出一個整數，表示答案。

Examples

input

thisisagarbagecompetitionhahaha

0 30 a

1 5 is

25 30 hah

6 12 ag

7 12 ag

output

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
char s[],ss[];
unsigned int h[],h2[],base[];
inline void init_hash(int l,char *s,unsigned int*h)
{
    h[] = ;
    for(int i=;i<=l;i++)
        h[i] = h[i-]*+s[i-];
    base[] = ;
    for(int i=;i<=l;i++)
        base[i] = base[i-]*;
}
inline unsigned int str(unsigned int*h,int l,int r)
{
    return h[r]-h[l]*base[r-l];
}
int main()
{
    cin>>s;
    init_hash(,s,h);
    int n;
    cin>>n;
    for(int i=;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        unsigned int p1 = str(h,l,r);
       // cout<<p1<<endl;
        cin>>ss;
        int len = strlen(ss);
        init_hash(len,ss,h2);
        unsigned int p2 = str(h2,,len);
        //cout<<p2<<endl;
        int sum = ;
        for(int ii=l;ii<=r+;ii++)
        {
            for(int j=ii+;j<=r+;j++)
            {
                     unsigned int p1 = str(h,ii,j);
                     if(p1==p2)sum++;
            }
        }
        cout<<sum<<endl;
    }

    return ;
}

C：

Prepared by ultmaster.

我們可以先考慮字元串有序的情況，比如是 aaabcc，我們隻要将字元串右移 3 位，變成 bccaaa，就做完了。那麼對于無序的情況，我們可以通過排序讓它有序，做完之後再排回去。

顯然最多的字母出現次數大于一半的情況是不行的。否則就将每個字母的位置和字母綁定一下，按字母序對結構體進行排序。然後右移「出現最多的字母出現次數」位，再排回來就可以了。時間複雜度 O(nlogn)。

也可以對 26 個字母進行周遊，把每個字母填到合适的位置。具體細節留給讀者思考。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int i;
    char e;
    char ee;
}s[];
char ss[];
int cmp(node a,node b)
{
    return a.e-'a'<b.e-'a';
}
int cmp2(node a,node b)
{
    return a.i<b.i;
}
int main()
{
   scanf("%s",ss);
   int book[]={};
   int len = strlen(ss);
   for(int i=;ss[i];i++)
   {
       s[i].i = i;
       s[i].e = ss[i];
       book[ss[i]-'a'+]++;
   }
   int mm = ;
   int ans ;
   for(int i=;i<=;i++)
   {
        if(book[i]>mm)
        {
            mm = book[i];
            ans = i;
        }
   }
   if(mm>len/)
    printf("impossible\n");
   else
   {
       //cout<<mm<<endl;
       sort(s,s+len,cmp);
//       for(int i=0;i<len;i++)
//       {
//           printf("%c",s[i].e);
//       }
//       cout<<endl;
       for(int i=;i<len;i++)
       {

           s[i].ee = s[(mm+i)%len].e;
       }
       sort(s,s+len,cmp2);
       for(int i=;i<len;i++)
       {
           printf("%c",s[i].ee);
       }
   }

    return ;
}

D 二分比對匈牙利比對模闆+因子分解（bzoj錦囊問題）

Time limit per test: 1.0 seconds

Memory limit: 256 megabytes

唐納德是一個數學天才。有一天，他的數學老師決定為難一下他。他跟唐納德說：「現在我們來玩一個遊戲。這個遊戲總共 n 輪，每一輪我都會給你一個數（第 i 輪給出的數是 ai）。你每次要回答一個數，是我給出的這個數的質因數，并且你說出的數不能重複。」

因為數學老師是刻意為難，是以這個遊戲很有可能不可能進行到最後。但是聰明的數學老師早就已經知道這個遊戲最多能進行幾輪了。現在他把問題抛給了你，想看看你知不知道。

注意，1 不是質數。

Input

輸入具有如下形式：

na1 a2 … an

第一行一個整數 n (1≤n≤3 000)。

第二行 n 個整數用空格隔開，a1,a2,…,an (2≤ai≤106)。

Output

輸出遊戲最多能進行幾輪。

Examples

input

7 6 3

output

input

2 2 2 2 2

output

Source

EOJ Monthly 2017.12

題解：

又到了喜聞樂見的套路題時刻。

一個很顯然的想法是對左邊的 n 輪和右邊個質因數之間建邊，便是一個二分圖，就是做比對。但是很遺憾，樸素的比對是錯誤的，因為存在一個順序問題。正确的做法是有一次如果不能找到比對，就直接跳出。這是一個非常經典的問題，具體證明可以自行搜尋 BZOJ 錦囊問題。

求素數可以使用樸素的 O(n−−√) 做法，用素數篩篩過頭了可能反而會逾時。因為素數不多，但素數的範圍比較大，如果直接照抄闆子每次都 memset 可能會逾時，可以打時間戳，或者直接對質數進行離散化。

也可以二分答案直接跑二分圖，姿勢好一點也能過。

#include<bits/stdc++.h>
using namespace std;
const int maxn = +;
vector<int> v[maxn],g[maxn];
int vis[maxn],a[maxn],l[maxn];
bool dfs(int u)
{
    for(int i=;i<g[u].size();i++)
    {
        int j = g[u][i];
        if(!vis[j])
        {
            vis[j]  =true;
            if(l[j]==-||dfs(l[j]))
            {
                l[j] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n;
    cin>>n;
    int ans;
    memset(l,-,sizeof(l));
    for(int i=;i<=n;i++)
    {
         scanf("%d",&a[i]);
         if(a[i]==)
         {
             n = i-;//出現1即跳出即可
             break;
         }
         for(int j=;j*j<=a[i];++j)
         {
             while(a[i]%j==)
             {
                 v[i].push_back(j);
                 a[i]/=j;
             }
         }
         if(a[i]!=)v[i].push_back(a[i]);
    }
         if(n==)
         {
             puts("0");
             return ;
         }
         for(int i=;i<=n;i++)
         {
            for(int j=;j<v[i].size();j++)
            {
                g[i].push_back(v[i][j]);
            }
            memset(vis,false,sizeof(vis));
            if(!dfs(i))break;
            else ans = i;
         }
         cout<<ans<<endl;


    return ;
}

【bzoj1191】[HNOI2006]超級英雄Hero

Description

現在電視台有一種節目叫做超級英雄,大概的流程就是每位選手到台上回答主持人的幾個問題,然後根據回答問題的多少獲得不同數目的獎品或獎金。主持人問題準備了若幹道題目，隻有當選手正确回答一道題後，才能進入下一題，否則就被淘汰。為了增加節目的趣味性并适當降低難度，主持人總提供給選手幾個“錦囊妙計”，比如求助現場觀衆，或者去掉若幹個錯誤答案（選擇題）等等。這裡，我們把規則稍微改變一下。假設主持人總共有m道題，選手有n種不同的“錦囊妙計”。主持人規定，每道題都可以從兩種“錦囊妙計”中選擇一種，而每種“錦囊妙計”隻能用一次。我們又假設一道題使用了它允許的錦囊妙計後，就一定能正确回答，順利進入下一題。現在我來到了節目現場，可是我實在是太笨了，以至于一道題也不會做，每道題隻好借助使用“錦囊妙計”來通過。如果我事先就知道了每道題能夠使用哪兩種“錦囊妙計”，那麼你能告訴我怎樣選擇才能通過最多的題數嗎？

Input

輸入檔案的一行是兩個正整數n和m(0 < n <1001,0 < m < 1001)表示總共有n中“錦囊妙計”，編号偉0~n-1，總共有m哥問題。

以下的m行，每行兩個數，分别表示第m個問題可以使用的“錦囊妙計”的編号。

注意，每種編号的“錦囊妙計”隻能使用一次，同一個問題的兩個“錦囊妙計”可能一樣。

Output

第一行為最多能通過的題數p

Sample Input

5 6

3 2

2 0

0 3

0 4

3 2

Sample Output

C++

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int mp[][],lk[];
int n,m;
bool y[];
bool find(int x)
{
    for(int i=;i<n;i++)
    {
       if(!y[i]&&mp[x][i])
       {
           y[i]=;
           if(!lk[i]||find(lk[i]))
           {
              lk[i]=x;
              return ;
           }
       }
    }
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)
    {
       int x,y;
       scanf("%d%d",&x,&y);
       mp[i][x]=mp[i][y]=;
}
    int ans=;
    for(int i=;i<=m;i++)
    {
        memset(y,,sizeof(y));
        if(find(i))ans++;
        else break;
    }
    printf("%d\n",ans);
    return ;
}

E：

參考部落格

E比昨天更多的棒棒糖（Easy+Hrad）（華師網絡賽）（DP||母函數||背包優化）

Time limit per test: 2.0 seconds

Memory limit: 512 megabytes

唐納德先生的某女性朋友最近與唐納德先生同居。該女性朋友攜帶一 baby。該 baby 酷愛吃棒棒糖，且有一個奇怪的特性：今天吃的棒棒糖一定要比昨天的棒棒糖更多，至少要一樣多。如果棒棒糖少了，baby 就會很不高興；另外如果有連續 k 天棒棒糖的數量都是一樣的，baby 也會很不高興。

唐納德先生發現他的口袋裡隻有可憐的 n 元錢，他可以用 1 元錢買 1 根棒棒糖。他想用這些錢逗 baby 開心，這些錢可以不花完。他可以從某一天開始再也不買棒棒糖，把他的女性朋友和 baby 一起送回家；但是他絕對不能讓 baby 不高興，否則他的女性朋友可能對他做一些不和諧的事情。

唐納德先生想要知道，他總共有多少種買棒棒糖的方案，兩種方案不相同當且僅當總天數不相同，或者某一天買的棒棒糖數量不相同。唐納德先生知道這個問題對于聰明的你實在是太簡單了，是以他加了一個附加條件：他第一天必須買棒棒糖，而且至少買 x 根棒棒糖。

Input

一行三個整數 n,x,k。

資料範圍約定：

對于 Easy 檔：1≤n,x≤100,2≤k≤100。

對于 Hard 檔：1≤n,x≤104,2≤k≤104。

Output

輸出答案模 998 244 353。

Examples

input

3 1 2

output

input

1 1 2

output

input

4 2 3

output

Note

樣例 1：

有四種方案：

第一天 1；

第一天 2；

第一天 3；

第一天 1，第二天 2；

注意第一天和第二天都買 1 是不行的，因為連續兩天棒棒糖數量一樣，baby 就會很不高興。

題意：

把n表示成a1*p1+a2*p2+a3*p3…的形式，且滿足x<=a1

Easy版本，普通母函數


#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int Mod=;
int c1[],c2[],ans,x,K,p;
int n,i,j,m,k;
void _get()
{  
    memset(c1,,sizeof(c1));
    memset(c2,,sizeof(c2));
    scanf("%d%d",&x,&K);
    for(k=;k<K&&k*x<=n;k++) {
         c1[k*x]=;
         ans=(ans+c1[k*x])%Mod;
    }
    for(i=x+;i<=n;i++){
        for(j=;j<=n;j++)
          for(k=;k*i+j<=n&&k<K;k++) {
               c2[k*i+j]+=c1[j]; 
               if(k) ans=(ans+c1[j])%Mod;
            }
        for(k=;k<=n;k++) {
            c1[k]=c2[k];    
            c2[k]=;
        }
    }
    ans=(ans+Mod-)%Mod;
}
int main()
{

    while(cin>>n) {
        ans=;
        _get(); 
        cout<<ans<<endl;
    }
    return ;
}


Hard版本，母函數優化背包。


include<cstdio>
include<cstdlib>
include<iostream>
include<cstring>
using namespace std;
const int Mod=;
const int maxn=;
long long  a[maxn],b[maxn],c[maxn],ans;
int main()
{
    int n,x,k,i,j;
    scanf("%d%d%d",&n,&x,&k);
    a[]=b[]=;

    for(i=x;i<=n;i++)
     for(j=n;j>=;j--)
      if(j>=i*k) a[j]=(a[j]-a[j-i*k])%Mod;

    for(i=x;i<=n;i++)
     for(j=i;j<=n;j++)
       b[j]=(b[j]+b[j-i])%Mod;

    for(i=;i<=n;i++)
     for(j=;j<=n;j++)
      if(i+j<=n) c[i+j]=(c[i+j]+a[i]*b[j])%Mod;

     for(i=;i<=n;i++)
       ans=((ans+c[i])%Mod+Mod)%Mod;

    printf("%lld\n",ans);
    return ;
}

EOJ Monthly 2017.12 (暨 ECNU 12 月内部選拔) 題解

比賽連結

題解連結

繼續閱讀

題解 DTOJ #2802. 區間（interval）

DTOJ2161 Christmas題目題解

DTOJ3312 行走題目題解

DTOJ3320 GotoAndPlay題目題解

2019年藍橋杯省賽個人題解

計算機作業系統（第四版）湯小丹編著第一章習題

洛谷P2272 [ZJOI2007]最大半連通子圖——題解

牛牛愛博弈

八數位難題————Astar算法好

jzoj5290 【NOIP2017提高組A組模拟8.17】行程的交集 (樹上路徑交，dfs序+樹狀數組維護姿勢)

POJ 1321棋盤問題（dfs）

題解：2012 ACM-ICPC Asia Dhaka Regional ContestWedding of SultanMemory OverflowPoker End GamesOverlapping CharactersLearning Vector

組合數與母函數

B - No Name UVALive - 6319 思維or連結清單

C++:NOIP2011

LeetCode——224. 基本電腦(Basic Calculator)[困難]——分析及代碼（Java）一、題目二、分析及代碼三、其他