Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

NKSP - Siêu đối xứng




Một xâu có độ dài lớn hơn 1 chỉ gồm các chữ cái la tinh in thường được gọi là đối xứng, nếu ta đọc xâu đó từ trái sang phải và từ phải sang trái là như nhau. Một xâu được gọi là siêu đối xứng, nếu nó là xâu đối xứng hoặc được tạo thành bằng cách ghép liên tiếp từ nhiều xâu đối xứng.

Yêu cầu: Cho một xâu S, hãy đếm số xâu con siêu đối xứng của S.( Xâu con của một xâu S là một đoạn liên tiếp các ký tự của S)

Dữ liệu

Chứa xâu S với độ dài không vượt quá 1000.

Kết quả

Ghi ra số xâu con tìm được.

Ví dụ

Dữ liệu
abc	
Kết quả
0

Dữ liệu
abacdc	
Kết quả
3
Submit solution!
Được gửi lên bởi:Jimmy
Ngày:2008-12-09
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:PTNK Team Selection 2008
hide comments
Xem lại 1  2  3  4 Xem tiếp >
2019-08-18 11:14:22
debug từ 65 lên 100 :)) mình giỏi vl :)) @hoangteo0103

Last edit: 2019-08-18 11:14:46
2019-08-18 11:06:34
//code ac cho ai can
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define II pair <int, int>
#define fi first
#define se second
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define fast_machine ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int N = 1e3 + 5;
int n, dp[N][N], f[N];
string st;
void in() {
cin >> st;
n = st.size(), st = ' ' + st;
}
void process() {
memset(dp, false, sizeof(dp));
FOD(i, n, 1){
for(int j = i; j <= n; j++){
if(i == j){
dp[i][j] = true;
continue;
}
if(i == j - 1){
if(st[i] == st[j]) dp[i][j] = true;
continue;
}
if(st[i] == st[j]) dp[i][j] = dp[i + 1][j - 1];
}
}
int res = 0, f[N][N];
FOR(i, 1, n) FOR(j, i + 1, n) FOR(t, j + 2, n){
f[i][t] = max(f[i][t], dp[i][j] & dp[j + 1][t]);
//if(f[i][t] == 1) cout << i << ' ' << j << ' ' << t << endl;
}
FOR(i, 1, n) FOR(j, i, n){
if((dp[i][j] || f[i][j]) && j - i >= 1) res++;
}
cout << res;
}
#undef int
int main() {
if(fopen("trash.inp", "r"))
freopen("trash.inp", "r", stdin), freopen("trash.out", "w", stdout);
#define int long long
in();
process();
}
2019-08-18 11:05:33
dijkstra acc ??? wtf ?? ioi ez
2019-08-18 11:04:56
n^4 acc ?? del thể tin được ?? tk ra đề ngu vl
2017-12-07 02:16:33
nhật hào sạch
2017-06-06 15:55:44
trâu cũng AC =)))
2017-01-20 18:07:00
1 cmn đấm :)
2016-10-10 18:45:51 Sơn Tùng M-TP
Tối ưu đi nào... :))
2016-10-04 15:34:17
tai sao cai thu hai ra 3 phai la 2 chu
2016-09-22 09:49:26
chỉ cần 1 chút xử lý với O(n^3) là AC rồi <3 :)) : D :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.