BZOJ 1695 [Usaco2007 Demo]Walk the Talk 链表+数学[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

题意:链接

方法:乱搞

解析:

出这道题的人存心报复社会。

首先这个单词表…先上网上找这个单词表…

反正总共2265个单词，然后就考虑怎么做就行了。

刚开始我没看表，找不到怎么做，最快的方法我也只是想到了类n^6的做法。

然后我就卡关辣，这关怎么过！

神犇的方法是:观察表，发现规律:

发现表中的单词最长就是4个字母。

所以我们可以考虑求1，2，3，4长度的单词数。

1的话可以直接记录，扫的时候顺带加上就行。

然后神犇说了一句话:

表中长度为4的单词前两个字母相同的单词个数不超过35个。

长度为3前一个字母相同的单词个数不超过7个。

所以直接上链表优化啊？

这样的话就要求我们预处理什么呢？

预处理点（i,j）右上角字母x的出现次数。

预处理点（i,j）右上角后缀xy的出现次数。

这个怎么维护啊？

容斥原理啊，所以复杂度在26*26*nm左右，也就是4次方，可以接受。

所以我们只需要枚举开头的两个字母，这是n^4的复杂度，然后再加上链表，枚举次数不超过43=(35+7)，而提取个数因为我们的预处理，变成辣O1啊，所以这样的话总共的复杂度是在n^5的！

掉了一个n啊！这不就能过了吗！

orz出题人。

单词表:

A
AA
AAA
AAAA
ABBE
ABED
ABET
ABLE
ABLY
ABUT
ACE
ACES
ACHE
ACID
ACME
ACNE
ACRE
ACT
AD
ADD
ADDS
ADO
ADS
AFAR
AFT
AGAR
AGE
AGED
AGER
AGES
AGO
AGOG
AGUE
AH
AID
AIDE
AIDS
AIL
AIM
AIMS
AIR
AIRS
AIRY
AJAR
AKIN
ALAS
ALBA
ALE
ALEE
ALGA
ALL
ALLY
ALMA
ALMS
ALOE
ALSO
ALUM
AM
AMEN
AMID
AMMO
AMOK
AMYL
AN
ANAL
AND
ANEW
ANON
ANT
ANTE
ANTI
ANTS
ANUS
ANY
APE
APED
APES
APEX
APSE
APT
AQUA
ARC
ARCH
ARCS
ARE
AREA
ARID
ARK
ARM
ARMS
ARMY
ART
ARTS
AS
ASH
ASK
ASKS
ASP
ASS
AT
ATE
ATOM
ATOP
AUNT
AURA
AUTO
AVER
AVID
AVOW
AWAY
AWE
AWED
AWL
AWLS
AWRY
AX
AXED
AXER
AXES
AXIS
AXLE
AXON
AYE
AYES
BABE
BABY
BACK
BAD
BADE
BAG
BAGS
BAH
BAIL
BAIT
BAKE
BALD
BALE
BALK
BALL
BALM
BAN
BAND
BANE
BANG
BANK
BANS
BAR
BARB
BARD
BARE
BARK
BARN
BARS
BASE
BASH
BASK
BASS
BAT
BATH
BATS
BAUD
BAWL
BAY
BAYS
BE
BEAD
BEAK
BEAM
BEAN
BEAR
BEAT
BEAU
BECK
BED
BEDS
BEE
BEEF
BEEN
BEEP
BEER
BEES
BEET
BEG
BEGS
BELL
BELT
BELY
BEND
BENT
BEST
BET
BETA
BETS
BEVY
BIAS
BIB
BIBS
BID
BIDE
BIDS
BIER
BIG
BIKE
BILE
BILK
BILL
BIN
BIND
BING
BINS
BIRD
BIT
BITE
BITS
BLAB
BLED
BLEW
BLIP
BLOB
BLOC
BLOT
BLOW
BLUE
BLUR
BOA
BOAR
BOAT
BOB
BOBS
BODE
BODY
BOG
BOGS
BOIL
BOLD
BOLL
BOLT
BOMB
BOND
BONE
BONG
BONY
BOO
BOOB
BOOK
BOOM
BOON
BOOR
BOOS
BOOT
BORE
BORN
BOSS
BOTH
BOUT
BOW
BOWL
BOWS
BOX
BOY
BOYS
BRA
BRAE
BRAG
BRAN
BRAS
BRAT
BRAY
BRED
BREW
BRIG
BRIM
BROW
BUCK
BUD
BUDS
BUFF
BUG
BUGS
BULB
BULK
BULL
BUM
BUMP
BUMS
BUN
BUNK
BUNS
BUNT
BUOY
BURL
BURN
BURP
BURY
BUS
BUSH
BUSS
BUST
BUSY
BUT
BUTT
BUY
BUYS
BUZZ
BY
BYE
BYTE
CAB
CABS
CAFE
CAGE
CAKE
CALF
CALL CALM CAM CAME CAMP CAN CANE CANS CANT CAP CAPE CAPS CAR CARD CARE CARP CARS CART CASE CASH CASK CAST CAT CATS CAVE CAW CEDE CELL CENT CHAP CHAR CHAT CHEF CHEW CHIC CHIN CHIP CHIT CHOP CHUM CITE CITY CLAD CLAM CLAN CLAP CLAW CLAY CLIP CLOD CLOG CLOT CLUB CLUE COAL COAT COAX COCA COCK COCO COD CODE COED COG COGS COIL COIN COKE COLD COLT COMB COME CON CONE COO COOK COOL COON COOP COP COPE COPS COPY CORD CORE CORK CORN COST COSY COT COTS COVE COW COWL COWS COZY CRAB CRAG CRAM CREW CRIB CROP CROW CRUD CRUX CRY CUB CUBE CUBS CUE CUED CUES CUFF CULL CULT CUP CUPS CURB CURD CURE CURL CURS CURT CUSP CUT CUTE CUTS CYST CZAR DAD DADS DALE DAM DAME DAMN DAMP DAMS DARE DARK DARN DART DASH DATA DATE DAWN DAY DAYS DAZE DEAD DEAF DEAL DEAN DEAR DEBT DECK DEED DEEM DEEP DEER DEFY DELL DEMO DEN DENS DENT DENY DESK DEUS DEW DEWY DIAL DICE DID DIE DIED DIEM DIES DIET DIG DIGS DIKE DILL DIM DIME DIMS DIN DINE DING DINT DIP DIPS DIRE DIRT DISC DISH DISK DIVE DO DOCK DOE DOER DOES DOG DOGS DOLE DOLL DOME DON DONE DONS DOOM DOOR DOPE DOSE DOT DOTE DOTS DOVE DOWN DOZE DRAB DRAG DRAM DRAW DREW DRIP DROP DRUG DRUM DRY DUAL DUB DUBS DUCK DUCT DUD DUE DUEL DUES DUET DUG DUKE DULL DULY DUMB DUMP DUNE DUNG DUNK DUPE DUSK DUST DUTY DYAD DYE DYED DYER DYES DYNE EACH EAR EARL EARN EARS EASE EAST EASY EAT EATS EBB EBBS ECHO EDDY EDGE EDIT EEL EELS EGG EGGS EGO EGOS EKE EKED EKES ELF ELK ELKS ELM ELMS ELSE EM EMIT EN END ENDS ENVY EPIC ERA ERAS ERE ERG ERGO ERR ERRS ESPY ET ETCH EVEN EVER EVIL EWE EWES EX EXAM EXEC EXIT EYE EYED EYER EYES FACE FACT FADE FAG FAGS FAIL FAIN FAIR FAKE FALL FAME FAN FANG FANS FAR FARE FARM FAST FAT FATE FATS FAUN FAWN FAZE FEAR FEAT FED FEE FEED FEEL FEES FEET FELL FELT FEN FEND FERN FEUD FEW FIAT FIB FIEF FIFE FIG FIGS FILE FILL FILM FIN FIND FINE FINK FINS FIR FIRE FIRM FISH FIST FIT FITS FIVE FIX FLAG FLAK FLAM FLAP FLAT FLAW FLAX FLEA FLED FLEE FLEW FLEX FLIP FLIT FLOG FLOP FLOW FLU FLUE FLUX FLY FOAL FOAM FOB FOCI FOE FOES FOG FOGS FOGY FOIL FOLD FOLK FOND FONT FOOD FOOL FOOT FOR FORD FORE FORK FORM FORT FOUL FOUR FOWL FOX FRAY FREE FRET FRO FROG FROM FRY FUEL FULL FUME FUN FUND FUNK FUR FURS FURY FUSE FUSS FUZZ GAB GAD GAG GAGS GAIN GAIT GALE GALL GAME GANG GAP GAPE GAPS GARB GAS GASH GASP GATE GAVE GAWK GAY GAZE GEAR GEL GELD GELS GEM GEMS GENE GENT GERM GET GETS GIFT GIG GILD GILL GILT GIN GINS GIRD GIRL GIRT GIST GIVE GLAD GLEE GLEN GLOW GLUE GLUT GNAT GNAW GNU GO GOAD GOAL GOAT GOD GODS GOES GOLD GOLF GONE GONG GOOD GOOF GORE GORY GOSH GOT GOUT GOWN GRAB GRAD GRAM GRAY GREW GREY GRID GRIM GRIN GRIP GRIT GROW GRUB GULF GULL GULP GUM GUMS GUN GUNS GURU GUSH GUST GUT GUTS GUY GUYS GYRO HA HACK HAD HAG HAIL HAIR HALE HALF HALL HALT HAM HAMS HAND HANG HAP HARD HARE HARK HARM HARP HART HAS HASH HAT HATE HATS HAUL HAVE HAWK HAY HAZE HAZY HE HEAD HEAL HEAP HEAR HEAT HECK HEED HEEL HEIR HELD HELL HELM HELP HEM HEMP HEMS HEN HENS HER HERB HERD HERE HERO HERS HEW HEWS HEX HEY HI HICK HID HIDE HIGH HIKE HILL HILT HIM HIND HINT HIP HIPS HIRE HIS HISS HIT HITS HIVE HOAR HOE HOES HOG HOGS HOLD HOLE HOLY HOME HOMO HONE HOOD HOOF HOOK HOOP HOOT HOP HOPE HOPS HORN HOSE HOST HOT HOUR HOW HOWL HUB HUBS HUE HUES HUG HUGE HUH HULL HUM HUMP HUMS HUNG HUNK HUNT HURL HURT HUSH HUSK HUT HUTS HYMN IBEX IBID IBIS ICE ICED ICES ICON ICY IDEA IDEM IDLE IDLY IDOL IF ILL ILLS ILLY IMP IMPS IN INCH INK INKS INN INNS INTO ION IONS IOTA IRE IRES IRIS IRK IRKS IRON IS ISLE IT ITCH ITEM ITS IVY JAB JABS JACK JADE JAIL JAM JAMS JAR JARS JAW JAWS JAY JAZZ JEAN JEEP JEER JERK JEST JET JETS JIG JIGS JOB JOBS JOG JOGS JOIN JOKE JOLT JOT JOTS JOY JOYS JUDO JUG JUGS JUMP JUNK JURE JURY JUST JUT KEEL KEEN KEEP KEN KEPT KERN KEY KEYS KICK KID KIDS KILL KIN KIND KING KINK KISS KIT KITE KITS KNEE KNEW KNIT KNOB KNOT KNOW KUDO LAB LABS LACE LACK LACY LAD LADS LADY LAG LAGS LAID LAIN LAIR LAKE LAMB LAME LAMP LAND LANE LAP LAPS LARD LARK LASH LASS LAST LATE LAVA LAW LAWN LAWS LAX LAY LAYS LAZY LEAD LEAF LEAK LEAN LEAP LED LEE LEEK LEER LEES LEFT LEG LEGS LEND LENS LENT LESS LEST LET LETS LEVY LEWD LIAR LICE LICK LID LIDS LIE LIED LIEN LIES LIEU LIFE LIFT LIKE LILY LIMB LIME LIMP LINE LINK LINT LION LIP LIPS LISP LIST LIT LIVE LOAD LOAF LOAN LOBE LOCI LOCK LOFT LOGO LOGS LOIN LONE LONG LOOK LOOM LOON LOOP LOOT LORD LORE LOSE LOSS LOST LOT LOTS LOUD LOUT LOVE LOW LOWS LUCK LULL LUMP LUNG LURE LURK LUSH LUST LUTE LYNX LYRE MACE MAD MADE MAID MAIL MAIM MAIN MAKE MALE MALL MALT MAMA MAN MANE MANY MAP MAPS MARE MARK MART MASH MASK MASS MAST MAT MATE MATH MATS MAUL MAZE ME MEAD MEAL MEAN MEAT MEEK MEET MELT MEMO MEN MEND MENS MENU MERE MESH MESS MET META METE METS MEW MEWS MICA MICE MID MIEN MIKE MILD MILE MILK MILL MIND MINE MINI MINK MINT MIRE MISS MIST MIX MOAN MOAT MOB MOBS MOCK MODE MOLD MOLE MONK MOO MOOD MOOT MOP MOPS MORE MORN MOSS MOST MOTH MOVE MOW MOWS MU MUCH MUCK MUD MUFF MUG MUGS MULE MULL MUNG MUSE MUSH MUSK MUST MUTE MUTT MY MYTH NAB NAG NAGS NAIL NAME NAP NAPS NARY NAVY NAY NEAR NEAT NECK NEED NEON NEST NET NETS NEW NEWT NEXT NICE NICK NIGH NIL NINE NIP NIPS NO NOD NODE NODS NON NONE NOOK NOON NOR NORM NOSE NOT NOTE NOUN NOW NU NUDE NULL NUMB NUN NUNS NUT NUTS OAF OAK OAKS OAR OARS OAT OATH OATS OBEY OBOE ODD ODDS ODE ODES ODOR OF OFF OFFS OFT OH OHM OIL OILS OILY OKAY OLD OLDY OMEN OMIT ON ONCE ONE ONES ONLY ONTO ONUS ONYX OOZE OPAL OPEN OPT OPTS OPUS OR ORAL ORB ORE ORES ORGY OUCH OUR OURS OUST OUT OUTS OVAL OVEN OVER OWE OWED OWES OWL OWLS OWN OWNS OX OXEN PACE PACK PACT PAD PADS PAGE PAID PAIL PAIN PAIR PAL PALE PALL PALM PALS PAN PANE PANG PANS PANT PAPA PAR PARE PARK PARS PART PASS PAST PAT PATE PATH PATS PAVE PAW PAWN PAWS PAY PAYS PEA PEAK PEAL PEAR PEAS PEAT PECK PEEK PEEL PEEP PEER PEG PEGS PELT PEN PEND PENS PENT PEP PER PERK PEST PET PETS PEW PEWS PHI PI PICA PICK PIE PIER PIES PIG PIGS PIKE PILE PILL PIMP PIN PINE PING PINK PINS PINT PION PIP PIPE PISS PIT PITH PITS PITY PLAN PLAY PLEA PLOD PLOT PLOW PLOY PLUG PLUM PLUS PLY POD PODS POEM POET POGO POKE POLE POLL POLO POMP POND PONG PONY POOL POOR POP POPS PORE PORK PORT POSE POSH POST POT POTS POUR POUT POX PRAY PREP PREY PRIM PRO PROD PROP PROS PROW PRY PUB PUBS PUFF PUKE PULL PULP PUMA PUMP PUN PUNS PUNT PUNY PUP PUPA PUPS PURE PURR PUS PUSH PUSS PUT PUTS PUTT PYRE QUA QUAD QUAY QUIP QUIT QUIZ QUO RACE RACK RAFT RAG RAGE RAGS RAID RAIL RAIN RAKE RAM RAMP RAMS RAN RANG RANK RANT RAP RAPE RAPS RAPT RARE RASH RASP RAT RATE RATS RAVE RAW RAY RAYS RAZE RE READ REAL REAM REAP REAR RED REDO REDS REED REEF REEL REIN RELY REND RENT REST RHO RIB RIBS RICE RICH RID RIDE RIDS RIFT RIG RIGS RILL RIM RIME RIMS RIND RING RINK RIOT RIP RIPE RIPS RISE RISK RITE ROAD ROAM ROAR ROB ROBE ROBS ROCK ROD RODE RODS ROE ROLE ROLL ROMP ROOF ROOK ROOM ROOT ROPE ROSY ROT ROTS ROUT ROVE ROW ROWS RUB RUBS RUBY RUDE RUE RUG RUGS RUIN RULE RUM RUMP RUN RUNG RUNS RUNT RUSH RUST RUT RUTS RYE SACK SAD SAFE SAG SAGA SAGE SAGS SAID SAIL SAKE SALE SALT SAME SAND SANE SANG SANK SAP SAPS SARI SASH SAT SATE SAVE SAW SAWS SAX SAY SAYS SCAB SCAN SCAR SCOW SCUD SEA SEAL SEAM SEAR SEAS SEAT SECT SEE SEED SEEK SEEM SEEN SEEP SEER SEES SELF SELL SEMI SEND SENT SEPT SERF SET SETS SEW SEWS SEX SEXY SHAM SHE SHED SHIN SHIP SHIT SHOD SHOE SHOP SHOT SHOW SHUN SHUT SHY SICK SIDE SIFT SIGH SIGN SILK SILL SILO SILT SINE SING SINK SINS SIP SIPS SIR SIRE SIRS SIT SITE SITS SITU SIX SIZE SKEW SKI SKID SKIM SKIN SKIP SKIS SKIT SKY SLAB SLAM SLAP SLAT SLAY SLED SLEW SLID SLIM SLIP SLIT SLOB SLOP SLOT SLOW SLUG SLUM SLUR SLY SMOG SMUG SMUT SNAG SNAP SNIP SNOB SNOW SNUB SNUG SO SOAK SOAP SOAR SOB SOBS SOCK SOD SODA SODS SOFA SOFT SOIL SOLD SOLE SOLO SOME SON SONG SONS SOON SOOT SORE SORT SOUL SOUP SOUR SOW SOWN SOY SOYA SPA SPAN SPAT SPEC SPED SPIN SPIT SPOT SPUN SPUR SPY STAB STAG STAR STAY STEM STEP STEW STIR STOP STOW STUB STUD STUN SUB SUBS SUCH SUCK SUDS SUE SUED SUES SUIT SULK SUM SUMS SUN SUNG SUNK SUNS SURE SURF SWAB SWAM SWAN SWAP SWAT SWAY SWIM SWUM TAB TABS TACK TACT TAG TAGS TAIL TAKE TALE TALK TALL TAME TAN TANG TANK TAP TAPE TAPS TAR TART TASK TAU TAUT TAX TAXI TEA TEAM TEAR TEAS TEEM TEEN TELL TEN TEND TENS TENT TERM TEST TEXT THAN THAT THAW THE THEM THEN THEY THIN THIS THUD THUG THUS TICK TIDE TIDY TIE TIED TIER TIES TILE TILL TILT TIME TIN TINS TINT TINY TIP TIPS TIRE TIT TITS TO TOAD TOE TOES TOIL TOLD TOLL TOMB TON TONE TONS TOO TOOK TOOL TOP TOPS TORE TORN TOSS TOUR TOW TOWN TOY TOYS TRAP TRAY TREE TREK TRIM TRIO TRIP TROD TROT TRUE TRY TUB TUBE TUBS TUCK TUFT TUG TUGS TUNE TURF TURN TWAS TWIG TWIN TWO TWOS TYPE TYPO UGH UGLY UNDO UNIT UNTO UP UPON URGE URN URNS US USE USED USER USES VAIN VALE VAN VANE VANS VARY VASE VAST VAT VATS VEAL VEER VEIL VEIN VENT VERB VERY VEST VETO VEX VIA VIAL VICE VIE VIED VIER VIES VIEW VILE VINE VISA VITA VOID VOLT VOTE VOW VOWS WADE WAFT WAG WAGE WAGS WAIL WAIT WAKE WALK WALL WAN WAND WANE WANT WAR WARD WARE WARM WARN WARP WARS WART WARY WAS WASH WASP WAVE WAX WAXY WAY WAYS WE WEAK WEAN WEAR WEB WEBS WEDS WEE WEED WEEK WEEP WELD WELL WENT WEPT WERE WEST WET WETS WHAT WHEN WHIM WHIP WHIT WHIZ WHO WHOM WHY WICK WIDE WIFE WIG WIGS WILD WILE WILL WILT WILY WIN WIND WINE WING WINK WINS WIPE WIRE WIRY WISE WISH WISP WIT WITH WITS WOE WOKE WOLF WOMB WON WONT WOO WOOD WOOF WOOL WOOS WORD WORE WORK WORM WORN WOVE WRAP WREN WRIT YANK YARD YARN YAWN YEA YEAR YEAS YELL YELP YES YET YOKE YON YOU YOUR ZEAL ZERO ZEST ZINC ZONE ZOO ZOOM ZOOS

代码:（因单词表在上方给出，所以此处略）

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 35
using namespace std;
string d[2265];
int map[N][N];
int sum1[N][N][N];
int sum2[N][N][N][N];
int fuck[N][N][N][N];
int head[N][N];
int head2[N][N];
int v[N];
int v1[N][N];
int cnt,cnt2;
int n,m;
struct node
{
    int fromx,fromy,x,y,next;
}edge[2265],edge2[2265];
void init()
{
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    cnt=1,cnt2=1;
}
void edgeadd(int fromx,int fromy,int to)
{
    edge[cnt].fromx=fromx,edge[cnt].fromy=fromy;
    edge[cnt].x=to;
    edge[cnt].next=head[fromx][fromy];
    head[fromx][fromy]=cnt++;
}
void edgeadd2(int fromx,int fromy,int to,int to2)
{
    edge2[cnt2].fromx=fromx,edge2[cnt2].fromy=fromy;
    edge2[cnt2].x=to,edge2[cnt2].y=to2;
    edge2[cnt2].next=head2[fromx][fromy];
    head2[fromx][fromy]=cnt2++;
}
char s[N];
int main()
{
    //此处放单词表，多背单词少刷水！！！！！！！！！！！！！！！！
    init();
    for(int i=0;i<=2264;i++)
    {
        int len=d[i].size();
        switch(len)
        {
            case 1:v[d[i][0]-'A']=1;break;
            case 2:v1[d[i][0]-'A'][d[i][1]-'A']=1;break;
            case 3:edgeadd(d[i][0]-'A',d[i][1]-'A',d[i][2]-'A');break;
            case 4:edgeadd2(d[i][0]-'A',d[i][1]-'A',d[i][2]-'A',d[i][3]-'A');break;
        }
    }
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
        {
            map[i][j]=s[j]-'A';
        }
    }
    for(int i=0;i<26;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=m;k>=1;k--)
            {
                sum1[i][j][k]=sum1[i][j-1][k]+sum1[i][j][k+1]-sum1[i][j-1][k+1]+(map[j][k]==i);
                fuck[map[j][k]][i][j][k]=sum1[i][j][k]-(map[j][k]==i);
            }
        }
    }
    for(int i=0;i<26;i++)
    {
        for(int j=0;j<26;j++)
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=m;l>=1;l--)
                {
                    sum2[i][j][k][l]=sum2[i][j][k-1][l]+sum2[i][j][k][l+1]-sum2[i][j][k-1][l+1]+fuck[i][j][k][l];
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(v[map[i][j]])ans++;
            for(int x=i;x>=1;x--)
            {
                for(int y=j;y<=m;y++)
                {
                    if(x==i&&y==j)continue;
                    if(v1[map[i][j]][map[x][y]])ans++;
                    for(int k=head[map[i][j]][map[x][y]];k!=-1;k=edge[k].next)
                    {
                        int to=edge[k].x;
                        ans+=sum1[to][x][y]-(map[x][y]==to);
                    }
                    for(int k=head2[map[i][j]][map[x][y]];k!=-1;k=edge2[k].next)
                    {
                        int to=edge2[k].x;
                        int to2=edge2[k].y;
                        ans+=sum2[to][to2][x][y]-fuck[to][to2][x][y];
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
}