[求救] UVA 10789

bac

題目

我的做法是
先建質數表，再用upper_bound找出有多少個，然後檢察是否為質數
不知道為什麼一直WA又找不出錯的測資
求解

[C++] 純文本查看 復制代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;


bool nprime[4096] = {false};


inline void init_prime()
{
        for(int i = 3 ; i < 64 ; i++)
                if(!nprime[i])
                        for(int k = 4095/i , j = i*k ; k>=i ; k--, j-=i)
                                if(!nprime[k])
                                        nprime[j] = true;
        for(int i = 4 ; i < 2500 ; i+=2)
                nprime[i] = true;
        nprime[1] = true;
}

int main()
{
        //init
        int time;
        char str[2015];
        
        init_prime();
        

        //process
        scanf("%d",&time);
        for(int t = 1 ; t <= time ; t++)
        {        
                bool empty = true;
        
                scanf("%s",str);
                int len = strlen(str);
                str[len] = 127;
                printf("Case %d: ", t);
                for(int i = 0 ; i < len ; )
                {
                        int j = upper_bound(str, str+len, str[i]) - str;
                //        printf("\n%c : %d\n", str[i] ,j-i);
                //        cout << "i=" << i << ", j=" << j << endl;
                        if(!nprime[j-i])
                        {
                                empty = false;
                                putchar(str[i]);
                        }
                        i = j;
                }
                
                if(empty)
                        printf("empty");
                putchar('\n');
        }
        
        return 0;
}

tntchn

我打 ccbbaa 之頪的就會顯示 empty
題目似乎沒有說不能從較後面的英文字母打回前面？