PKU 2406 Power Strings
解法
暇つぶし(暇じゃないのに)やったやるだけ問題。
シミュレートするだけ。が、しかしstringのsubstr()つかってやって2TLE出しました…。
こういう問題で手こずるとJOI予選落ちるんじゃないかって気がしてとても焦ります…。
自分が経験して困ったことなので書いておきますが、PKU(POJ)ではC,C++の場合入出力は、必ずprintfまたはscanf関数を使うことをオススメします。自分はコレを知らずに初めてPKUの問題を解いた時に20個ぐらいの謎TLEを出しました。
あと、今日重み付きUnion-Findという言葉を聞いたのですが誰か知ってる方よかったら教えてくださいm(_ _)m
ソースコード
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #include <string> #include <sstream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <functional> #include <iostream> #include <map> #include <set> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define sz(x) ((int)(x).size()) #define fi first #define sec second #define SORT(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define EQ(a,b) (abs((a)-(b))<EPS) int main() { while(1) { char str[1000005]; scanf("%s",str); int len=strlen(str); if(len==1&&str[0]=='.')break; for(int i=1;i<=len;i++) { if(len%i!=0)continue; int now=0; while(now<len&&str[now%i]==str[now])now++; if(now==len) { printf("%d\n",len/i); break; } } } return 0; }