导语
打的还可以，但是犯了不少基本错误，输入没读完就输出，翻译错误，未取模出现负数，精度范围等等，需要引以为戒，但这场收获不小
涉及的知识点
链接：大连站
题目
A
题目大意：n个点，给出m对关系，每对关系代表这两个点一定不在同一集合中，给出x个点代表这x个点一定在A集合中，给出y个点代表和y个点一定在B集合中，判断能否把这n个点分成A,B两个集合
思路：并查集的基本题，注意虚点的使用即可
代码
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,x,y,f[2424];
int type[2424];
int Seek(int x) {
return f[x]==x?x:f[x]=Seek(f[x]);
}
void Union(int x,int y) {
int fx=Seek(x),fy=Seek(y);
if(fx!=fy)
f[fx]=fy;
}
void solve() {
bool flag=0;
int xx=x,yy=y;
memset(type,0,sizeof(type));
for(int i=1; i<=2*n; i++)
f[i]=i;
while(m--) {
int a,b;
scanf("%d%d",&a,&b);
if(Seek(a)==Seek(b))
flag=1;
Union(a,b+n);
Union(b,a+n);
}
if(n==1) {
printf("YES\n");
return ;
}
if(x==0&&y==0) {
int fx=Seek(1),fxx=Seek(1+n);
type[fx]=1;
type[fxx]=-1;
}
while(x--) {
int a;
scanf("%d",&a);
int fx=Seek(a),fxx=Seek(a+n);
if(type[fx]==-1||type[fxx]==1)
flag=1;
type[fx]=1;
type[fxx]=-1;
}
while(y--) {
int a;
scanf("%d",&a);
int fx=Seek(a),fxx=Seek(a+n);
if(type[fx]==1||type[fxx]==-1)
flag=1;
type[fx]=-1;
type[fxx]=1;
}
if(flag) {
printf("NO\n");
return ;
}
for(int i=1; i<=n; i++) {
int fx=Seek(i);
if(type[fx]==0) {
flag=1;
printf("NO\n");
return;
}
}
printf("YES\n");
}
int main() {
while(~scanf("%d%d%d%d",&n,&m,&x,&y)) {
solve();
}
return 0;
}
B
题目大意：给出一个正则表达式，求一个字符串中所有的匹配
思路：shift-and算法（第一次听说）
共九个数字，将每个数字在整个长度中出现的位置置1，未出现过的置0，将答案清空，每次左移一位并将最低位置1，将当前答案与匹配的字符的对应数组进行与运算
如果答案的第i位为1，代表从这一位开始向前长度i+1的串可以和当前正则表达式的前缀匹配，将最低位置1，只有当每一步都匹配了，这个1才会继续传递下去，一直传递到第n-1位就代表都匹配了
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e6+5;
int n;
bitset<1212>b[11],res;
char s[maxn];
int main() {
while(~scanf("%d",&n)) {
for(int i=0; i<10; i++)b[i].reset();
for(int i=0; i<n; i++) {
int x;
scanf("%d",&x);
for(int j=0; j<x; j++) {
int y;
scanf("%d",&y);
b[y].set(i);
}
}
scanf(" %s",s);
res.reset();
for(int i=0; s[i]; i++) {
res=res<<1;
res.set(0);
res=res&b[s[i]-'0'];
if(res[n-1]==1) {
char ch=s[i+1];
s[i+1]='\0';
puts(s+i-n+1);
s[i+1]=ch;
}
}
}
return 0;
}
C
题目大意：略
思路：威佐夫博弈模板，但是本题要求高精度，计算的数据需要精确到小数点后100位，这里只解释一下为什么要精确到这么多位，因为给出的数据范围很大，所以在计算减法时产生的数据也可能很大，也就是位数很多，那么套用的黄金分割比如果位数不足的话，最差情况下会有几十位的整形数据被置0，这样带来的误差是非常大的
代码
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
BigDecimal TWO = BigDecimal.valueOf(2);
BigDecimal FIVE = BigDecimal.valueOf(5);
double d=Math.pow(10,-100);
BigDecimal EPS = BigDecimal.valueOf(d);
BigDecimal L = new BigDecimal("2");
BigDecimal R = new BigDecimal("3");
BigDecimal mid = null;
while(R.subtract(L).compareTo(EPS) > 0)
{
mid = L.add(R).divide(TWO);
if(mid.multiply(mid).compareTo(FIVE) < 0)
L=mid;
if(mid.multiply(mid).compareTo(FIVE) > 0)
R = mid;
}
BigDecimal GOLD = mid.add(BigDecimal.ONE).divide(TWO);
BigDecimal a,b;
String str1,str2;
Scanner input = new Scanner(System.in);
while(input.hasNext())
{
str1 = input.next();
str2 = input.next();
a = new BigDecimal(str1);
b = new BigDecimal(str2);
if(solve(a,b,GOLD))
{
System.out.println("1");
}
else{
System.out.println("0");
}
}
}
static boolean solve(BigDecimal a,BigDecimal b,BigDecimal gold)
{
BigDecimal d = a.subtract(b);
if(d.compareTo(BigDecimal.valueOf(0))==-1){
d=d.multiply(BigDecimal.valueOf(-1));
}
d = d.multiply(gold);
BigInteger dd = d.toBigInteger();
d = new BigDecimal(dd.toString());
if (!d.equals(a.min(b))) return true;
else return false;
}
}
E
题目大意：将序列
1
,
2
,
…
,
n
1,2,\dots,n
1,2,…,n依次放入一些集合当中，当添加
i
i
i的时候，需要创建一个新的集合，然后将
i
i
i放入，并且与此同时将
[
i
?
l
o
w
b
i
t
(
i
)
+
1
,
i
?
1
]
[i-lowbit(i)+1,i-1]
[i?lowbit(i)+1,i?1]从原先的集合中拿出来并一起放在新集合中，每次将一个整数放入一个新集合，花费为1，但取出不需要花费，在进行n次操作之后，现在有q次询问，询问有两种
- 1 L R 询问添加所有的
[
L
,
R
]
[L,R]
[L,R]的数需要的花费
- 2 x 计算将x放入集合的所有花费
思路：根据题意，操作1为询问
[
L
,
R
]
[L,R]
[L,R]中所有数的
l
o
w
b
i
t
lowbit
lowbit之和，操作2为x在树状数组中被多少个点管辖
对于操作1，如果直接累和lowbit显然会超时，那么能否通过前缀和的思路来求解？
先来看一下lowbit的定义，lowbit求出来的是二进制中从右到左首次出现的1对应的十进制数值，那么求前n个数的lowbit前缀和就相当于求前n个数中：1首次出现在第0位次数，1首次出现在第1位次数，1首次出现在第2位次数…，如果1首次出现在第i位，那么该数一定是
2
i
2^i
2i的倍数，而不是
2
i
?
1
2^{i-1}
2i?1的倍数，那么前n个数中
2
i
2^i
2i倍数的个数减去
2
i
+
1
2^{i+1}
2i+1倍数的个数就是1首次出现在第i位的次数
对于操作2，其实求的是其祖先节点有多少个，用树状数组的性质一直向上查找即可
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int sum(int x) {
int ans=0;
for(int i=1; i<=x; i<<=1)
ans+=(x/i-x/(i<<1))*i;
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,q;
while( cin >>n>>q) {
while(q--) {
int x,y,res=0;
cin >>x;
if(x==1) {
int l,r;
cin >>l>>r;
res=sum(r)-sum(l-1);
} else {
cin >>y;
for(int i=y; i<=n; i+=(i&-i))res++;
}
cout <<res<<endl;
}
}
return 0;
}
G
题目大意：给出有n个节点的树，每个点有点权，一共有k种点权，现在从树上选一个点作为起点沿着边遍历，每个点只能经过一次，需要收集每种点权，最后会在一个点停下来，询问一共有多少种方案，两种方案被视为不同当起点不同或终点不同
思路：使用状态压缩+点分治，状态压缩位运算的性质使得很好统计对于当前状态是否存在另一状态使得整体或满足题设条件，详细见题解，已经讲的较为清晰了
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e4+5;
int n,k,val[maxn],cnt,head[maxn],res,rt,S;
int Size[maxn],f[maxn],rec[1212];
vector<int>vec;
bool vis[maxn];
struct node {
int next,to;
} e[maxn<<1];
void Add(int from,int to) {
e[++cnt].next=head[from];
e[cnt].to=to;
head[from]=cnt;
}
void getroot(int u,int fa) {
Size[u]=1;
f[u]=0;
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(vis[v]||v==fa)continue;
getroot(v,u);
Size[u]+=Size[v];
f[u]=max(f[u],Size[v]);
}
f[u]=max(f[u],S-Size[u]);
if(f[u]<f[rt])
rt=u;
}
void getval(int u,int fa,int s) {
vec.push_back(s);
rec[s]++;
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(vis[v]||v==fa)continue;
getval(v,u,s|val[v]);
}
}
int getsum(int u,int s) {
vec.clear();
memset(rec,0,sizeof(rec));
getval(u,0,s);
int len=vec.size(),ans=0,t=(1<<k)-1;
for(int i=0; i<len; i++) {
rec[vec[i]]--;
ans+=rec[t];
for(int j=vec[i]; j; j=(j-1)&vec[i])
ans+=rec[j^t];
rec[vec[i]]++;
}
return ans;
}
void solve(int u) {
vis[u]=1;
res+=getsum(u,val[u]);
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(!vis[v]) {
res-=getsum(v,val[u]|val[v]);
rt=0,S=Size[v];
getroot(v,0);
solve(rt);
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
while(cin >>n>>k) {
cnt=0;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(Size,0,sizeof(Size));
for(int i=1; i<=n; i++) {
cin >>val[i];
val[i]--;
val[i]=1<<val[i];
}
for(int i=0; i<n-1; i++) {
int u,v;
cin >>u>>v;
Add(u,v);
Add(v,u);
}
if(k==1)cout <<n*n<<endl;
else {
res=0,rt=1,S=n;
f[0]=0x3f3f3f3f;
getroot(1,0);
solve(rt);
cout <<res<<endl;
}
}
return 0;
}
参考文献
- Regular Number–hdu5972
- 2016 大连 E HDU 5975 Aninteresting game · 树状数组
- Aninteresting game HDU - 5975 (树状数组lowbit深入理解)
- Garden of Eden
|