調查問卷

Accepts: 1546 Submissions: 6596 Time Limit: 6500/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Problem Description

度度熊為了完成畢業論文，需要收集一些資料來支撐他的論據，于是設計了一份包含 mm 個問題的調查問卷，每個問題隻有 'A' 和 'B' 兩種選項。

将問卷散發出去之後，度度熊收到了 nn 份互不相同的問卷，在整理結果的時候，他發現可以隻保留其中的一部分問題，使得這 nn 份問卷仍然是互不相同的。這裡認為兩張問卷是不同的，當且僅當存在至少一個被保留的問題在這兩份問卷中的回答不同。

現在度度熊想知道，存在多少個問題集合，使得這 nn 份問卷在隻保留這個集合的問題之後至少有 kk 對問卷是不同的。

Input

第一行包含一個整數 TT，表示有 TT 組測試資料。

接下來依次描述 TT 組測試資料。對于每組測試資料：

第一行包含三個整數 nn，mm 和 kk，含義同題目描述。

接下來 nn 行，每行包含一個長度為 mm 的隻包含 'A' 和 'B' 的字元串，表示這份問卷對每個問題的回答。

保證 1 \leq T \leq 1001≤T≤100，1 \leq n \leq 10^31≤n≤103，1 \leq m \leq 101≤m≤10，1 \leq k \leq 10^61≤k≤106，給定的 nn 份問卷互不相同。

Output

對于每組測試資料，輸出一行資訊 "Case #x: y"（不含引号），其中 x 表示這是第 xx 組測試資料，y 表示滿足條件的問題集合的個數，行末不要有多餘空格。

Sample Input

2
2 2 1
AA
BB
2 2 2
AA
BB

Sample Output

Case #1: 3
Case #2: 0

可以把這些情況都2進制壓位，那麼就可以直接求出來了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1005
int b[1<<10],dp[N][1<<10];;
char s[N][15];
int main()
{
    int T,ca=0,n,m,K;
    scanf("%d",&T);
    while(T--)
    {
        int i,j,k;
        scanf("%d%d%d",&n,&m,&K);
        for(i=1; i<=n; i++)scanf("%s",s[i]);
        memset(dp,0,sizeof(dp));
        for(i=1; i<(1<<m); i++)
        {
            memset(b,0,sizeof(b));
            for(j=1; j<=n; j++)
            {
                int S=0;
                for(k=0; k<m; k++)
                    if((i&(1<<k))&&s[j][k]=='A')S|=1<<k;
                b[S]++;
                dp[j][i]=dp[j-1][i]+j-b[S];
            }
        }
        int ans=0;
        for(i=1; i<(1<<m); i++)if(dp[n][i]>=K) ans++;
        printf("Case #%d: %d\n",++ca,ans);
    }
    return 0;
}

子串查詢

Accepts: 4145 Submissions: 17054 Time Limit: 3500/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Problem Description

度度熊的字元串課堂開始了！要以像度度熊一樣的天才為目标，努力奮鬥哦！

為了檢驗你是否具備不聽課的資質，度度熊準備了一個隻包含大寫英文字母的字元串 A[1,n] = a_1 a_2 \cdots a_nA[1,n]=a1a2⋯an，接下來他會向你提出 qq 個問題 (l,r)(l,r)，你需要回答字元串 A[l,r] = a_l a_{l+1} \cdots a_rA[l,r]=alal+1⋯ar 内有多少個非空子串是 A[l,r]A[l,r] 的所有非空子串中字典序最小的。這裡的非空子串是字元串中由至少一個位置連續的字元組成的子序列，兩個子串是不同的當且僅當這兩個子串内容不完全相同或者出現在不同的位置。

記 |S|∣S∣ 為字元串 SS 的長度，對于兩個字元串 SS 和 TT ，定義 SS 的字典序比 TT 小，當且僅當存在非負整數 k(\leq \min(|S|,|T|))k(≤min(∣S∣,∣T∣)) 使得 SS 的前 kk 個字元與 TT 的前 kk 個字元對應相同，并且要麼滿足 |S| = k∣S∣=k 且 |T| > k∣T∣>k，要麼滿足 k < \min(|S|,|T|)k<min(∣S∣,∣T∣) 且 SS 的第 k+1k+1 個字元比 TT 的第 k+1k+1 個字元小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。

Input

第一行包含一個整數 TT，表示有 TT 組測試資料。

接下來依次描述 TT 組測試資料。對于每組測試資料：

第一行包含兩個整數 nn 和 qq，表示字元串的長度以及詢問的次數。

第二行包含一個長為 nn 的隻包含大寫英文字母的字元串 A[1,n]A[1,n]。

接下來 qq 行，每行包含兩個整數 l_i,r_ili,ri，表示第 ii 次詢問的參數。

保證 1 \leq T \leq 101≤T≤10，1 \leq n,q \leq 10^51≤n,q≤105，1 \leq l_i \leq r_i \leq n1≤li≤ri≤n。

Output

對于每組測試資料，先輸出一行資訊 "Case #x:"（不含引号），其中 x 表示這是第 xx 組測試資料，接下來 qq 行，每行包含一個整數，表示字元串 A[l,r]A[l,r] 中字典序最小的子串個數，行末不要有多餘空格。

Sample Input

Sample Output

Case #1:
1
1
1

B我還傻不拉幾RMQ？其實直接循環就好啦

#include<stdio.h>
#define min(a,b) a<b?a:b
const int N=2e5+5;
char s[N];
int dmi[N][30],f[N];
int sum[30][N];
int n,q;
void RMQ_init()
{
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+j-1<=n; i++)
            dmi[i][j]=min(dmi[i][j-1],dmi[i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r)
{
    int k=f[r-l+1];
    return min(dmi[l][k],dmi[r-(1<<k)+1][k]);
}
int main()
{
    int T,ca=0;
    f[0]=-1;
    scanf("%d",&T);
    while(T--)
    {
        printf("Case #%d:\n",++ca);
        scanf("%d%d%s",&n,&q,s+1);
        for(int i=1; i<=n; i++)
        {
            dmi[i][0]=s[i]-'A',f[i]=((i&(i-1))==0)?f[i-1]+1:f[i-1];
            for(int j=0; j<26; j++)sum[j][i]=sum[j][i-1]+(s[i]-'A'==j);
        }
        RMQ_init();
        for(int i=0,l,r,z; i<q; i++)scanf("%d%d",&l,&r),z=RMQ(l,r),printf("%d\n",sum[z][r]-sum[z][l-1]);
    }
    return 0;
}

HackStatus

三原色圖

Accepts: 708 Submissions: 2974 Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Problem Description

度度熊有一張 nn 個點 mm 條邊的無向圖，所有點按照 1,2,\cdots,n1,2,⋯,n 标号，每條邊有一個正整數權值以及一種色光三原色紅、綠、藍之一的顔色。

現在度度熊想選出恰好 kk 條邊，滿足隻用這 kk 條邊之中的紅色邊和綠色邊就能使 nn 個點之間兩兩連通，或者隻用這 kk 條邊之中的藍色邊和綠色邊就能使 nn 個點之間兩兩連通，這裡兩個點連通是指從一個點出發沿着邊可以走到另一個點。

對于每個 k=1,2,\cdots,mk=1,2,⋯,m，你都需要幫度度熊計算選出恰好 kk 條滿足條件的邊的權值之和的最小值。

Input

第一行包含一個正整數 TT，表示有 TT 組測試資料。

接下來依次描述 TT 組測試資料。對于每組測試資料：

第一行包含兩個整數 nn 和 mm，表示圖的點數和邊數。

接下來 mm 行，每行包含三個整數 a,b,wa,b,w 和一個字元 cc，表示有一條連接配接點 aa 與點 bb 的權值為 ww、顔色為 cc 的無向邊。

保證 1 \leq T \leq 1001≤T≤100，1 \leq n,m \leq 1001≤n,m≤100，1 \leq a,b \leq n1≤a,b≤n，1 \leq w \leq 10001≤w≤1000，c \in {R,G,B}c∈{R,G,B}，這裡 R,G,BR,G,B 分别表示紅色、綠色和藍色。

Output

對于每組測試資料，先輸出一行資訊 "Case #x:"（不含引号），其中 x 表示這是第 xx 組測試資料，接下來 mm 行，每行包含一個整數，第 ii 行的整數表示選出恰好 ii 條滿足條件的邊的權值之和的最小值，如果不存在合法方案，輸出 -1−1，行末不要有多餘空格。

Sample Input Copy

Sample Output

Case #1:
-1
-1
-1
9
10
12
17
22

跑兩次最小生成樹，但是一直wa啊，原來是Case，首字母大寫

#include<bits/stdc++.h>
using namespace std;
const int N=105,INF=0x3f3f3f3f;
int t,n,m,dsu[N],ans[N];
bool vis[N];
struct Edge
{
    int u,v,w,typ;
    void read()
    {
        char ch;
        scanf("%d%d%d %c",&u,&v,&w,&ch);
        typ=(ch=='R'?1:(ch=='G'?2:4));
    }
    bool operator<(Edge const &t)const
    {
        return w<t.w;
    }
} e[N];
int dsu_find(int x)
{
    return dsu[x]<0?x:(dsu[x]=dsu_find(dsu[x]));
}
bool dsu_merge(int u,int v)
{
    u=dsu_find(u),v=dsu_find(v);
    if(u==v)return 0;
    if(dsu[u]<dsu[v])
        swap(u,v);
    dsu[v]-=dsu[u]==dsu[v];
    dsu[u]=v;
    return 1;
}
void solve(int msk)
{
    int cnt=0,sum=0;
    memset(vis,0,sizeof vis);
    memset(dsu,-1,sizeof dsu);
    for(int i=0; i<m; i++)
        if((e[i].typ&msk)&&dsu_merge(e[i].u,e[i].v))
        {
            ++cnt;
            sum+=e[i].w;
            vis[i]=1;
        }
    if(cnt<n-1)return;
    if(ans[cnt]>sum)ans[cnt]=sum;
    for(int i=0; i<m; i++)
        if(!vis[i])
        {
            ++cnt;
            sum+=e[i].w;
            vis[i]=1;
             if(ans[cnt]>sum)ans[cnt]=sum;
        }
}
int main()
{
    scanf("%d",&t);
    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)e[i].read();
        sort(e,e+m);
        memset(ans,0x3f,sizeof ans);
        solve(3);
        solve(6);
        printf("Case #%d:\n",ca);
        for(int i=1; i<=m; i++)printf("%d\n",ans[i]<INF?ans[i]:-1);
    }
    return 0;
}

序列計數

Accepts: 313 Submissions: 1947 Time Limit: 4500/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Problem Description

度度熊了解到，11,22,…,nn 的排列一共有 n! = n \times (n-1) \times \cdots \times 1n!=n×(n−1)×⋯×1 個。現在度度熊從所有排列中等機率随機選出一個排列 p_1p1,p_2p2,…,p_npn，你需要對 kk=11,22,33,…,nn 分别求出長度為 kk的上升子序列個數，也就是計算滿足 1 \leq a_11≤a1 < a_2a2 < … < a_kak \leq n≤n 且 p_{a_1}pa1 <p_{a_2}p

轉載于:https://www.cnblogs.com/BobHuang/p/9501108.html

2018"百度之星"程式設計大賽 - 資格賽調查問卷子串查詢三原色圖序列計數

調查問卷

子串查詢

三原色圖

序列計數

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method