程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [BestCoder] Round #11

[BestCoder] Round #11

編輯：C++入門知識

[BestCoder] Round #11

輸出Yes只有一種情況.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define rd(x) scanf(%d,&x)
#define rd2(x,y)  scanf(%d%d,&x,&y)
#define rd3(x,y,z) scanf(%d%d%d,&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
//關鍵點是中點吧
int n,m,x,y;


int main()
{
    while(cin>>n>>m>>x>>y)
    {
        if(2*x==n&&2*y==m)
            cout<

1002
http://acm.hdu.edu.cn/showproblem.php?pid=5055
給出n個數字（每個數字0~9），用這n個數字組成一個數，要求不能有前導0，且最後一位必須是奇數。不能組成則輸出-1.
可以構造出數的情況有： 只有一個數，且該數是奇數；n個數中大於0的數至少有2個，且n個數中存在奇數。
如果能滿足的話，那麼最小的奇數做數的最後一位，剩下的數從大到小排在前面就是所求的數。
寫的時候邏輯有點亂.....這類題寫的時候一定得考慮全面一些。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define rd(x) scanf(%d,&x)
#define rd2(x,y)  scanf(%d%d,&x,&y)
#define rd3(x,y,z) scanf(%d%d%d,&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
const int maxn=102;
int num[maxn];
bool hasodd;
int minodd;
int n;

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    while(rd(n)!=EOF)
    {
        hasodd=0;
        minodd=100;//最小的奇數
        int p=-1;//最小的奇數的位置
        int cnt=0;//大於0的數字有多少個
        for(int i=1;i<=n;i++)
        {
            rd(num[i]);
            if(num[i]>0)
                cnt++;
            if(num[i]&1)
            {
                hasodd=1;
                if(minodd>num[i])
                   {
                       minodd=num[i];
                       p=i;
                   }

            }
        }
        if(n==1)
        {   if(hasodd)
            cout<=2&&hasodd)
        {
            swap(num[p],num[n]);
            sort(num+1,num+n,cmp);
            for(int i=1;i<=n;i++)
                cout<1003
 
給出一個只有小寫字母組成的字符串，然後給出一個數字k，問有多少子串滿足  該子串中相同字母出現的次數不超過k。比如有一個子串 abac k=2的話，a的次數=2不超過k,b,c的次數均為1，也不超過k，所以這個子串就是符合要求的.
一個長度為n的字符串，子串一共有n(n+1)/2個，題目中n是100000，直接枚舉肯定不行。
一開始想的也是枚舉，枚舉每個位置，判斷以該位置開頭的子串有多少個，兩重循環，第二重循環就是長度了,一開始以為長度最多就是26（26個字母），復雜度還可以，但是忘了k的事...k不一定等於1啊，有可能很大....所以悲劇了，果斷超時..
看到解題報告是 也是枚舉每個位置，統計的則是以該位置為結尾的最大子串的長度，則是以該位置結尾的所有子串的個數，這個好理解，比如k=2,   bcca,當位置為a時，滿足條件的最大子串為 bcca，長度為4，那麼滿足的所有子串的個數也為4，分別為  bcca  cca  ca  a。開辟兩個指針，一個是枚舉的位置，一個是滿足該位置的最大串的起始位置，處治為該串的第一個位置。mapmp,記錄每個字母出現的次數.下面以具體例子來說明是怎麼工作的吧,解釋不清楚.....
比如串   abbcbcc  k=2
一開始位置為1, 'a'，起始指針start為1，mp['a']++,  該值滿足<=k，ans+=     i-start+1  ；即ans+=1,對應的串為a
後來位置為2，'b',    起始指針start為1， mp['b']++,  滿足條件，   ans+= 2-start+1；       即ans+=2,對應的串為  b     ab
後來位置為3，也滿足條件，ans+=3,對應的串為  b  bb  abb
後來位置為4， 也滿足條件，ans+=4;對應的串為 c bc bbc abbc
後來位置為5， mp['b']++,這時候mp[b]=3,  3>k,不符合條件，原因是b這個字母多了一個，要想以該位置為結尾，那麼就得從前面去掉一個b，要求最大串，所以去掉最前面的一個b，同時更新起始位置， 這時候起始位置還是1，要想符合條件，就得移動該指針，mp['a']--,這是起始指針start對應的位置，start++, 這時候start=2,對應的字母為b，找到第一個b了，要把它去掉，所以再執行一次 mp['b']--,start++, 這時候start=3, 符合題意了， 滿足的最大串為
 bcb,   ans+= 5-start+1,即ans+=3 ,對應的子串為  b   cb   bcb
後來同理....
從上面流程中可以看出start指針是一直往前的，這個效率比前面說的那個要高，有些位置滿足的子串數可以0(1)來計算出
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define rd(x) scanf(%d,&x)
#define rd2(x,y)  scanf(%d%d,&x,&y)
#define rd3(x,y,z) scanf(%d%d%d,&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
char s[100004];
mapmp;
int len;
int k;
ll ans;
int main()
{
    int t;rd(t);
    while(t--)
    {
        mp.clear();
        scanf(%s,s+1);
        rd(k);
        len=strlen(s+1);
        int start=1;
        ans=0;
        for(int i=1;i<=len;i++)
        {
            mp[s[i]]++;
            if(mp[s[i]]>k)
            {
                while(s[start]!=s[i])
                {
                    mp[s[start]]--;
                    start++;
                }
                mp[s[start]]--;
                start++;
            }
            ans+=i-start+1;
        }
        printf(%I64d
,ans);
    }
    return 0;
}