bzoj2012: [Ceoi2010]Pin
2024-10-20 00:23:16
Description
给出N(2<=N<=50000)个长度为4的字符串，问有且仅有D(1<=D<=4)处不相同的字符串有几对。
Input
第1行： N，D 以下N行每行一个字符串
Output
一个数：有多少对有且仅有处不相同的字符串。
记录每个字符串出现次数以及带1..4个通配符的字符串出现次数，容斥得到答案
#include<cstdio>
int n,m;
char s[];
int _t2[][][];
int _t3[][];
int t4,ans=;
#define t3(a,b) _t3[a][b]
#define t2(a,b,c) _t2[a][b][c]
const int P=;
struct Map{
int xs[P],ys[P];
int&operator()(int a,int b,int c,int d){
int x=(((a<<|b)<<|c)<<)|d;
int w=x%P;
while(xs[w]){
if(xs[w]==x)return ys[w];
w+=;
if(w>=P)w-=P;
}
xs[w]=x;
return ys[w];
}
}t0,t1;
int main(){
scanf("%d%d",&n,&m);
for(t4=;t4<n;t4++){
scanf("%s",s);
int a=s[],b=s[],c=s[],d=s[];
if(!a||!b||!c||!d)printf("%d",a/=);
if(m==){
ans+=
-t0(a,b,c,d)++*
+t1(a,b,c,)++
+t1(a,b,d,)++
+t1(a,c,d,)++
+t1(b,c,d,)++;
}else if(m==){
int aa1,aa2,aa3;
ans+=
+(aa1=t0(a,b,c,d)++)*
-(aa2=t1(a,b,c,)++
+t1(a,b,d,)++
+t1(a,c,d,)++
+t1(b,c,d,)++)*
+(aa3=t2(a,b,)++
+t2(a,c,)++
+t2(a,d,)++
+t2(b,c,)++
+t2(b,d,)++
+t2(c,d,)++);
}else if(m==){
ans+=
-t0(a,b,c,d)++*
+(t1(a,b,c,)++
+t1(a,b,d,)++
+t1(a,c,d,)++
+t1(b,c,d,)++)*
-(t2(a,b,)++
+t2(a,c,)++
+t2(a,d,)++
+t2(b,c,)++
+t2(b,d,)++
+t2(c,d,)++)*
+t3(a,)++
+t3(b,)++
+t3(c,)++
+t3(d,)++;
}else{
ans+=
t0(a,b,c,d)++
-(t1(a,b,c,)++
+t1(a,b,d,)++
+t1(a,c,d,)++
+t1(b,c,d,)++)
+(t2(a,b,)++
+t2(a,c,)++
+t2(a,d,)++
+t2(b,c,)++
+t2(b,d,)++
+t2(c,d,)++)
-(t3(a,)++
+t3(b,)++
+t3(c,)++
+t3(d,)++)
+t4;
}
}
printf("%d\n",ans);
return ;
}
最新文章
- tableView显示第一个cell有偏移问题
- __clone()方法和传址区别
- jQuery的4种事件绑定方法
- 天气预报API获取
- Linux内核装载和启动一个可执行程序
- BeagleBone Black– 智能家居控制系统 LAS - ESP8266 UDP 服务
- Linux-NTP-Server+Client
- java5 新特性
- Windows 环境下于虚拟环境安装源码安装 cx_oracle
- Balanced Lineup(最简单的线段树题目)
- Hadoop基本概念
- Solr5.2.1+Zookeeper3.4.8分布式集群搭建
- Django_'utf-8' codec can't decode 问题解决
- php的调试工具xdebug
- 小a的子序列 （线性dp）
- Cnblog-Latex数学公式使用测试
- type__字符串
- wParam与lParam的区别
- Python3基础 list 访问列表中的列表的元素
- python学习笔记（八）---关于Django的下载以及环境配置