P3498 [POI2010]KOR-Beads

来源:http://www.cnblogs.com/huihao/archive/2017/07/09/7143420.html
-Advertisement-
Play Games

題目描述 Zxl有一次決定製造一條項鏈,她以非常便宜的價格買了一長條鮮艷的珊瑚珠子,她現在也有一個機器,能把這條珠子切成很多塊(子串),每塊有k(k>0)個珠子,如果這條珠子的長度不是k的倍數,最後一塊小於k的就不要拉(nc真浪費),保證珠子的長度為正整數。 Zxl喜歡多樣的項鏈,為她應該怎樣選擇數 ...


題目描述

Zxl有一次決定製造一條項鏈,她以非常便宜的價格買了一長條鮮艷的珊瑚珠子,她現在也有一個機器,能把這條珠子切成很多塊(子串),每塊有k(k>0)個珠子,如果這條珠子的長度不是k的倍數,最後一塊小於k的就不要拉(nc真浪費),保證珠子的長度為正整數。 Zxl喜歡多樣的項鏈,為她應該怎樣選擇數字k來儘可能得到更多的不同的子串感到好奇,子串都是可以反轉的,換句話說,子串(1,2,3)和(3,2,1)是一樣的。寫一個程式,為Zxl決定最適合的k從而獲得最多不同的子串。 例如:這一串珠子是: (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1), k=1的時候,我們得到3個不同的子串: (1),(2),(3) k=2的時候,我們得到6個不同的子串: (1,1),(1,2),(2,2),(3,3),(3,1),(2,3) k=3的時候,我們得到5個不同的子串: (1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2) k=4的時候,我們得到5個不同的子串: (1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)

輸入輸出格式

輸入格式:

 共有兩行,第一行一個整數n代表珠子的長度,(),第二行是由空格分開的顏色ai(1<=ai<=n)。

輸出格式:

也有兩行,第一行兩個整數,第一個整數代表能獲得的最大不同的子串個數,第二個整數代表能獲得最大值的k的個數,第二行輸出所有的k(中間有空格)。

輸入輸出樣例

輸入樣例#1:
21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1
輸出樣例#1:
6 1
2

題解:

枚舉長度+哈希

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
const int maxn=200000+5;
const int B=200191;
typedef unsigned long long ull;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ull mul[maxn],s1[maxn],s2[maxn];
int n,mx,num;
int a[maxn],b[maxn];
gp_hash_table<ull,bool>mp;
ull gethash(int l,int r)
{
    ull t;
    if(l<=r) t=s1[r]-s1[l-1]*mul[r-l+1];
    else
    t=s2[r]-s2[l+1]*mul[l-r+1];
    return t;
}
void solve(int x)
{
    if(mx*x>n) return;
    int ans=0;
    mp.clear();
    for(int i=1;i<=n;i+=x)
    if(i+x-1<=n)
    {
        ull t=gethash(i,i+x-1)*gethash(i+x-1,i);
        if(mp[t]) continue;
        else ans++;
        mp[t]=1;
    }
    if(ans>mx) mx=ans,num=0;
    if(ans==mx) b[++num]=x;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    mul[0]=1;
    for(int i=1;i<=n;i++) mul[i]=mul[i-1]*B;
    for(int i=1;i<=n;i++)
        s1[i]=s1[i-1]*B+a[i];
    for(int i=n;i>=1;i--)
        s2[i]=s2[i+1]*B+a[i];
    for(int i=1;i<=n;i++) solve(i);
    printf("%d %d\n",mx,num);
    for(int i=1;i<=num;i++)
    {
        printf("%d",b[i]);
        if(i!=num) printf(" ");
    }
    return 0;
}
    

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • MySQL的簡單使用 1. 使用MySQL命令行工具 Windows 用戶使用: MySQL Client, 輸入密碼 Linux: mysql u用戶名 p密碼 mysql uroot p 2. 顯示資料庫命令 show databases; 3. 創建資料庫命令 create database ...
  • 錯誤截圖如下: 步驟1. 打開瀏覽器,輸入http://www.adobe.com/cn/ 步驟2. 點擊菜單,打開下拉的列表,找到並點擊Adobe Flash Player 步驟3. 把可選程式的勾“√”去掉,否則會安裝可選程式,然後點擊立即安裝按鈕 步驟4. 上一步下載的文件還不是Adobe F ...
  • 使用nmcli命令配置網路 NetworkManager是管理和監控網路設置的守護進程,設備既就是網路介面,連接是對網路介面的配置,一個網路介面可以有多個連接配置,但同時只有一個連接配置生效。 1 配置主機名 CentOS6 之前主機配置文件:/etc/sysconfig/network CentO ...
  • 命令歷史、文件類查看工具、文件和目錄類管理工具、通配符、IO重定向 ...
  • 發佈遇到的問題1: HTTP 錯誤 404.17 - Not Found 請求的內容似乎是腳本,因而將無法由靜態文件處理程式來處理。 最終解決時IIS的設置情況: 1、應用程式池的高級設置中 啟用32位應用程式: True 托管管道模式: Classic 載入用戶配置文件: True 2、選中發佈的 ...
  • 主題: 需求: 用戶角色,講師\學員, 用戶登陸後根據角色不同,能做的事情不同,分別如下講師視圖 管理班級,可創建班級,根據學員qq號把學員加入班級 可創建指定班級的上課紀錄,註意一節上課紀錄對應多條學員的上課紀錄, 即每節課都有整班學員上, 為了紀錄每位學員的學習成績,需在創建每節上課紀錄是,同時 ...
  • TensorFlow實現Softmax Regression(回歸)識別手寫數字。MNIST(Mixed National Institute of Standards and Technology database),簡單機器視覺數據集,28X28像素手寫數字,只有灰度值信息,空白部分為0,筆跡根 ...
  • 在java中,有兩種創建String類型變數的方式: 第一種方式創建String變數時,首先查找JVM方法區的字元串常量池是否存在存放"abc"的地址,如果存在,則將該變數指向這個地址,不存在,則在方法區創建一個存放字面值"abc"的地址。 第二種方式創建String變數時,在堆中創建一個存放"ab ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...