2016大连

• 导语
• 涉及的知识点
• 题目
• • • A
    • B
    • C
    • E
    • G
• 参考文献

导语

打的还可以，但是犯了不少基本错误，输入没读完就输出，翻译错误，未取模出现负数，精度范围等等，需要引以为戒，但这场收获不小

涉及的知识点

链接：大连站

题目

A

题目大意：n个点，给出m对关系，每对关系代表这两个点一定不在同一集合中，给出x个点代表这x个点一定在A集合中，给出y个点代表和y个点一定在B集合中，判断能否把这n个点分成A,B两个集合

思路：并查集的基本题，注意虚点的使用即可

代码

#include #define ll long long#define INF 0x3f3f3f3fusing 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) {//如果没有给出信息，那么假设节点1位好，其虚点为坏 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 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);//第0位置1     res=res&b[s[i]-'0'];     if(res[n-1]==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) {// TODO Auto-generated method stubBigDecimal 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,\dots ,n$依次放入一些集合当中，当添加$i$的时候，需要创建一个新的集合，然后将$i$放入，并且与此同时将$[i-lowbit(i)+1,i-1]$从原先的集合中拿出来并一起放在新集合中，每次将一个整数放入一个新集合，花费为1，但取出不需要花费，在进行n次操作之后，现在有q次询问，询问有两种

1. 1 L R 询问添加所有的$[L,R]$的数需要的花费
2. 2 x 计算将x放入集合的所有花费

思路：根据题意，操作1为询问$[L,R]$中所有数的$lowbit$之和，操作2为x在树状数组中被多少个点管辖
对于操作1，如果直接累和lowbit显然会超时，那么能否通过前缀和的思路来求解？
先来看一下lowbit的定义，lowbit求出来的是二进制中从右到左首次出现的1对应的十进制数值，那么求前n个数的lowbit前缀和就相当于求前n个数中：1首次出现在第0位次数，1首次出现在第1位次数，1首次出现在第2位次数…，如果1首次出现在第i位，那么该数一定是 2 i 2^i 2i的倍数，而不是 2i−1 2^{i-1} 2i−1的倍数，那么前n个数中 2 i 2^i 2i倍数的个数减去 2i+1 2^{i+1} 2i+1倍数的个数就是1首次出现在第i位的次数
对于操作2，其实求的是其祖先节点有多少个，用树状数组的性质一直向上查找即可

代码

#include #define int long longusing namespace std;int sum(int x) {    int ans=0;    for(int i=1; i<=x; i<<=1)//次数乘上lowbit值 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 #define int long longusing 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]);//获得删除u之后的最大子树的大小    if(f[u]<f[rt])//重心定义 rt=u;}void getval(int u,int fa,int s) {//统计子树中从根向下的各种点权数    //这里的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);//传入u的点权    int len=vec.size(),ans=0,t=(1<<k)-1;    for(int i=0; i<len; i++) { rec[vec[i]]--; //拿到一个状态，尝试判断u的子树中存在多少路径得到的和与vec[i]相或得到所有种类点权 ans+=rec[t];//加上空集的数量，也就是不用经过u，只有一边路径即可满足条件 //每个点都加一次，之后会去重 for(int j=vec[i]; j; j=(j-1)&vec[i])//枚举当前状态的子集     ans+=rec[j^t];//判断是否存在u从另一条路径出发得到的和与j或能够得到所有种类点权 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);//得到v为根子树的重心     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，正好第1位是1     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;}

参考文献

1. Regular Number–hdu5972
2. 2016 大连 E HDU 5975 Aninteresting game · 树状数组
3. Aninteresting game HDU - 5975 (树状数组lowbit深入理解)
4. Garden of Eden