QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181906 | #6635. Strange Keyboard | ucup-team134 | WA | 570ms | 215484kb | C++14 | 6.1kb | 2023-09-17 03:40:53 | 2023-09-17 03:40:54 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=1e6+10;
ll inf=2e18;
const int maxalp=30;
int link[maxn],nxt[maxn][maxalp],isleaf[maxn],cnt=1,root=0;
int par[maxn],cpar[maxn],len[maxn];
ll val[maxn];
void ins(int x,string &s,vector<ll>&cost){
int c=0;
while(1){
if(c==s.size()){
return;
}
int sc=s[c]-'a';
if(nxt[x][sc]==-1){
par[cnt]=x;
cpar[cnt]=sc;
len[cnt]=c+1;
nxt[x][sc]=cnt++;
}
x=nxt[x][sc];
val[x]=min(val[x],cost[c]);
c=c+1;
}
}
int get_link(int x);
int get_nxt(int x,int c){
if(nxt[x][c]!=-1)return nxt[x][c];
if(x==0)return 0;
return nxt[x][c]= get_nxt(get_link(x),c);
}
int get_link(int x){
if(link[x]!=-1)return link[x];
if(x==0)return -1;
if(par[x]==0)return 0;
return link[x]= get_nxt(get_link(par[x]),cpar[x]);
}
void reset_aho(){
for(int i=0;i<cnt;i++){
link[i]=-1;
for(int j=0;j<maxalp;j++)nxt[i][j]=-1;
val[i]=inf;
len[i]=-1;
}
cnt=1;
}
struct bla{
vector<int>a;
int pt=0;
void clear(){
a.clear();
pt=0;
}
void pop_front(){
pt++;
}
void pop_back(){
a.pop_back();
if(a.size()<pt)pt=a.size();
}
void push_back(int c){
a.pb(c);
}
int size(){
return max((int)a.size()-pt,0);
}
int front(){
return a[pt];
}
int back(){
return a.back();
}
}deq[maxn];
int e=0;
int n,k;
string s[maxn];
ll dp[maxn],tmp[maxn];
ll rdp[maxn];
/*void upd_dp(int w,int c){
for(int i=0;i<w;i++)deq[i].clear();
int msum=w*c+k;
if(e)printf("%d %d WC\n",w,c);
for(int i=0;i<msum;i++)tmp[i]=inf;
for(int i=0;i<msum;i++){
if(e){
for(int j=1;j<=c;j++){
if(i-j*w>=0)tmp[i]=min(tmp[i],min(dp[i],dp[i-j*w]+j) );
}
}
else{
int cid=i%w;
while(deq[cid].size() && (i-deq[cid].front())/w>c)deq[cid].pop_front();
int id=-1;
if(deq[cid].size())id=deq[cid].front();
if(id!=-1)tmp[i]=min(dp[i], dp[id]+((i-id)/w) );
while(deq[cid].size() && (dp[deq[cid].back()]+(ll)(i-deq[cid].back()))/w>=dp[i] ){
deq[cid].pop_back();
}
deq[cid].push_back(i);
}
}
/// preradi tmp
for(int i=0;i<msum;i++)
if(tmp[i]!=inf)
dp[i%k]=min(dp[i%k],tmp[i]+(ll)i/k);
}*/
int pcnt=0;
void upd_dp(int w){
int msum=2*k;
//if(e)printf("%d %d WC\n",w,c);
ll pom=w/k;
w%=k;
for(int i=0;i<msum;i++)tmp[i]=inf;
for(int i=0;i<k;i++){
if(dp[i]>=inf)continue;
tmp[i+w]=min(tmp[i+w],min(dp[i+w],dp[i]+1+pom) );
///pcnt++;
}
/// preradi tmp
for(int i=0;i<k;i++){
///pcnt++;
if(tmp[i]!=inf)
dp[i]=min(dp[i],tmp[i]);
}
for(int i=0;i<k;i++){
///pcnt++;
if(tmp[k+i]!=inf)
dp[i]=min(dp[i],tmp[k+i]+1);
}
}
int main(){
memset(link,-1,sizeof(link));
memset(nxt,-1,sizeof(nxt));
memset(len,-1,sizeof(len));
for(int i=0;i<maxn;i++)val[i]=inf;
///freopen("test.txt","r",stdin);
int t;
scanf("%d",&t);
if(t==10)e=1;
while(t--){
scanf("%d %d",&n,&k);
vector<int>cand;
int sum=0;
int pb[2]={0,0};
for(int i=1;i<=n;i++){
cin>>s[i];
cand.pb(s[i].size());
sum+=s[i].size();
if(e){
pb[s[i][0]-'a']=1;
}
}
for(int i=0;i<=sum;i++)dp[i]=inf;
reset_aho();
sort(cand.begin(),cand.end());
vector<pii>cand2;
cand2.pb({cand[0],1});
for(int i=1;i<cand.size();i++){
if(cand[i]==cand2.back().ff)cand2[cand2.size()-1].ss++;
else cand2.pb({cand[i],1});
}
///printf("OP\n");
dp[0]=0;
for(int i=0;i<cand2.size();i++){
int x=cand2[i].ff;
for(int j=0;(1<<j)<=k;j++){
upd_dp((1<<j)*x);
pcnt++;
}
}
///printf("OP\n");
for(int i=1;i<=n;i++){
vector<ll>cost;
for(int j=0;j<s[i].size();j++){
ll d=((int)s[i].size())-j-1;
ll cc=d/k;
d%=k;
if(d==0){
cost.pb(cc+1);
continue;
}
d=(k-d)%k;
cost.pb(dp[d]+cc+2);
}
if(e){
//printf("%lld %c | %d COST\n",cost[0],s[i][0],s[i].size()%k);
}
ins(root,s[i],cost);
}
///printf("OPALA\n");
if(e){
///for(int i=1;i<cnt;i++)val[i]=1;
}
string qr;
cin>>qr;
int curr=root;
for(int i=1;i<=qr.size();i++)rdp[i]=inf;
rdp[0]=0;
for(int i=1;i<=qr.size();i++){
curr=get_nxt(curr,qr[i-1]-'a');
int pom=curr;
while(pom!=root){
rdp[i]=min(rdp[i],rdp[ i-len[pom]]+val[pom]);
pom=get_link(pom);
}
}
if(e){
// printf("%d %d PBPB\n",pb[0],pb[1]);
}
if(rdp[qr.size()]>=inf)printf("-1\n");
else printf("%lld\n",rdp[qr.size()]);
}
if(e)printf("%d CCC\n",pcnt);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 207940kb
input:
2 2 3 defgh abc abcde 1 1 a b
output:
3 -1
result:
ok 2 number(s): "3 -1"
Test #2:
score: 0
Accepted
time: 208ms
memory: 215484kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: -100
Wrong Answer
time: 570ms
memory: 210924kb
input:
10 446 4905 afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica afigcjhcgagabbiccehjcjajigghgbj...
output:
3 2 2 11 6 5 1 1 1 1 57980 CCC
result:
wrong output format Expected integer, but "CCC" found