wannafly挑战赛14

第一次打wannafly。。觉得自己好菜啊。。。

题目描述

在三维空间中，平面 x = 0, y = 0, z = 0，以及平面 x + y + z = K 围成了一个三棱锥。
整天与整数打交道的小明希望知道这个三棱锥内、上整点的数目。
他觉得数量可能很多，所以答案需要对给定的 M 取模。

输入描述:

输入有 1 ≤ T ≤ 10

⁵

 组数据。
每组数据中，输入两个整数 0 ≤ K ≤ 10

⁹

 + 7, 1 ≤ M ≤ 10

⁹

 + 7，意义如题目描述。

输出描述:

对于每组数据，输出一个整数，为三棱锥内、上整点的数目对 M 取模。

示例1

输入

输出

签到题吧。对于这个三棱锥，除了x=0,y=0,z=0外的斜平面上，他有(k+1)列，由上往下数第i列包含i个点，于是我们斜平面上有点 $ sum^{k+1}_{i=1} i= frac{(k+1)(k+2)}{2} $ 。因此给三棱锥等距地切出k个和斜平面平行的平面，因此三棱锥上的所有点分布在这(k+1）个平面上，于是从下往上数第i个平面上的点数为 $ frac{(i)(i+1)}{2} $ 对其求和，即$ sum^{k+1}_{i=1} frac{(i)(i+1)}{2} = frac{ sum^{k+1}_{i=1} (i)(i+1)}{2} = frac{ (k+1)(k+2)(k+3) }{6} $ 因此按照公式写答案2333.

 1 #include<bits/stdc++.h>
 2 #define clr(x) memset(x,0,sizeof(x))
 3 #define clr_1(x) memset(x,-1,sizeof(x))
 4 #define mod 1000000007
 5 #define LL long long
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 const int N=1e5+10;
 9 int T;
10 LL ans,k,m,dt,a[4];
11 int main()
12 {
13     ios::sync_with_stdio(false);
14     cin>>T;
15     while(T--)
16     {
17         cin>>k>>m;
18         ans=1;
19         for(int i=1;i<=3;i++)
20             a[i]=k+i;
21         for(int i=1;i<=3;i++)
22             if(a[i]%2==0)
23             {
24                 a[i]/=2;
25                 break;
26             }
27         for(int i=1;i<=3;i++)
28             if(a[i]%3==0)
29             {
30                 a[i]/=3;
31                 break;
32             }
33         ans=a[1]*a[2]%m*a[3]%m;
34         cout<<ans<<endl;
35     }
36 }

View Code

题目描述

在一个 Minecraft 村庄中，村长有这一本小写字母构成的名册（字符串的表），
每个名字旁边都记录着这位村民的声望值，而且有的村民还和别人同名。
随着时间的推移，因为没有村民死亡，这个名册变得十分大。

现在需要您来帮忙维护这个名册，支持下列 4 种操作：

1. 插入新人名 s_i，声望为 a_i
2. 给定名字前缀 p_i 的所有人的声望值变化 d_i
3. 查询名字为 s_j村民们的声望值的和（因为会有重名的）
4. 查询名字前缀为 p_j的声望值的和

输入描述:

第一行为两个整数 0 ≤ N ≤ 10

⁵

，表示接下来有 N 个操作；
接下来 N 行，每行输入一个操作，行首为一个整数 1 ≤ o

 ≤ 4，表示这一行的操作的种类，

那么这一行的操作和格式为：

1. 插入人名，这一行的格式为 1 s_i a_i，其中 |a_i| ≤ 10³
2. 前缀修改声望，这一行的格式为 2 p_i d_i，其中 |d_i| ≤ 10³
3. 查询名字的声望和，这一行的格式为 3 s_j
4. 查询前缀的声望和，这一行的格式为 4 p_j

输入保证插入人名的字符串的长度和小于或等于 10⁵，总的字符串的长度和小于或等于 10⁶。

输出描述:

对于每一次询问操作，在一行里面输出答案。

示例1

输入

20
1 a -10
1 abcba -9
1 abcbacd 5
4 a
2 a 9
3 aadaa
3 abcbacd
4 a
3 a
2 a 10
3 a
2 a -2
2 d -8
1 ab -2
2 ab -7
1 aadaa -3
4 a
3 abcba
4 a
4 c

输出

给trie做类似线段树的tag标记。
我们维护五个量，分别是当前节点路径字符串的数量、声望和，当前节点为前缀字符串的数量、声望和，以及标记tag。对于所有操作，操作的时候访问到当前点有tag的时候就往后面的节点pushdown。操作一在插入基础上pushdown。操作二像线段树一样，如果当前前缀存在，我们修改路径上的所有节点的值，并在终点处留下加上声望值的tag。三四操作就在pushdown后查询当前点的前缀声望和和前缀声望和。

  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x,0,sizeof(x))
  3 #define clr_1(x) memset(x,-1,sizeof(x))
  4 #define mod 1000000007
  5 #define LL long long
  6 #define INF 0x3f3f3f3f
  7 using namespace std;
  8 const int N=1e6+10;
  9 const int type=26;
 10 int T;
 11 struct node
 12 {
 13     int next[type];
 14     LL tag,sum,num,presum,prenum;
 15 }trie[N];
 16 int tot;
 17 char s[N];
 18 int n,m;
 19 LL d;
 20 void init()
 21 {
 22     tot=0;
 23     memset(&trie[0],0,sizeof(trie[0]));
 24     return ;
 25 }
 26 int makenode()
 27 {
 28     ++tot;
 29     memset(&trie[tot],0,sizeof(trie[tot]));
 30     return tot;
 31 }
 32 void pushdown(int now)
 33 {
 34     int p;
 35     if(trie[now].tag)
 36     {
 37         for(int i=0;i<type;i++)
 38         {
 39             p=trie[now].next[i];
 40             if(p)
 41             {
 42                 trie[p].tag+=trie[now].tag;
 43                 trie[p].sum+=trie[p].num*trie[now].tag;
 44                 trie[p].presum+=trie[p].prenum*trie[now].tag;
 45             }
 46         }
 47         trie[now].tag=0;
 48     }
 49     return ;
 50 }
 51 void add(char *s,LL d)
 52 {
 53     int now=0,p;
 54     for(int i=0;s[i];i++)
 55     {
 56         p=s[i]-'a';
 57         if(!trie[now].next[p])
 58             trie[now].next[p]=makenode();
 59         now=trie[now].next[p];
 60         pushdown(now);
 61         trie[now].presum+=d;
 62         trie[now].prenum++;
 63     }
 64     trie[now].sum+=d;
 65     trie[now].num++;
 66     return ;
 67 }
 68 void change(char *s,LL d)
 69 {
 70     int now=0,p;
 71     int i;
 72     for(i=0;s[i];i++)
 73     {
 74         p=s[i]-'a';
 75         if(!trie[now].next[p])
 76             break;
 77         now=trie[now].next[p];
 78         pushdown(now);
 79     }
 80     if(!s[i])
 81     {
 82         trie[now].tag+=d;
 83         int nowto=0;
 84         for(i=0;s[i];i++)
 85         {
 86             p=s[i]-'a';
 87             nowto=trie[nowto].next[p];
 88             trie[nowto].presum+=trie[now].prenum*d;
 89         }
 90         trie[now].sum+=d*trie[now].num;
 91     }
 92     return ;
 93 }
 94 LL query(char *s)
 95 {
 96     int now=0,p;
 97     int i;
 98     for(i=0;s[i];i++)
 99     {
100         p=s[i]-'a';
101         if(!trie[now].next[p])
102             break;
103         now=trie[now].next[p];
104         pushdown(now);
105     }
106     if(s[i])
107         return 0;
108     else
109         return trie[now].sum;
110 }
111 LL querypre(char *s)
112 {
113     int now=0,p;
114     int i;
115     for(i=0;s[i];i++)
116     {
117         p=s[i]-'a';
118         if(!trie[now].next[p])
119             break;
120         now=trie[now].next[p];
121         pushdown(now);
122     }
123     if(s[i])
124         return 0;
125     else
126         return trie[now].presum;
127 }
128 int main()
129 {
130     ios::sync_with_stdio(false);
131     cin>>n;
132     init();
133     for(int i=1;i<=n;i++)
134     {
135         cin>>m;
136         if(m==1)
137         {
138             cin>>s>>d;
139             add(s,d);
140         }
141         else if(m==2)
142         {
143             cin>>s>>d;
144             change(s,d);
145         }
146         else if(m==3)
147         {
148             cin>>s;
149             cout<<query(s)<<endl;
150         }
151         else
152         {
153             cin>>s;
154             cout<<querypre(s)<<endl;
155         }
156     }
157     return 0;
158 }

View Code

题目描述

codeJan有一天脑洞大开，想到一个有趣的问题。给一个固定根为1号结点的树，定义一个子树的beauty是这个子树的根节点到所有这棵树上其他节点的距离和，叶子节点的beauty是0。定义一个子树的sub-beauty是这个子树的beauty值减去这个子树的某一个子树(不包括自身)的beauty值。显然一个子树的beauty值是唯一的，而sub-beauty值可以有很多个。codeJan想要知道所有子树的所有sub-beauty中不超过m的最大值。

输入描述:

第一行是一个T≤20代表测试组数。每组测试的第一行包含两个正整数是n,m(n≤10

⁵

,m≤10

⁸

)，接下来n−1
行每行包含三个正整数a b d，分别表示a结点和b结点之间的距离是d,a,b∈[1,n],1≤d≤10

。请注意每棵树的根节点都是1号结点，并且保证输入合法。

输出描述:

对于每组测试样例输出一个整数表示所有子树sub-beauty中不超过m的最大值。如果所有子树的sub-beauty都大于m，输出-1。

示例1

输入

输出

3
-1 
6

我们一次dfs求出所有点的beauty，然后我们第二次dfs，并保存根到当前点的路径上的点的beauty。由于这个beauty是非递增的，因此我们直接查询大于等于当前点u的sum[u] m的值在路径bueauty的位置，然后+1即为相减后最靠近m的值了。由于我傻了没发现递增。。于是我写了一个权值线段树维护orz。

  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x,0,sizeof(x))
  3 #define clr_1(x) memset(x,-1,sizeof(x))
  4 #define mod 1000000007
  5 #define LL long long
  6 #define INF 0x3f3f3f3f
  7 #define pb(x) push_back(x)
  8 #define mp(x,y) make_pair(x,y)
  9 using namespace std;
 10 const int N=1e5+10;
 11 vector<pair<int,LL>> edge[N];
 12 LL sum[N],cnum[N],val[N];
 13 int n,T,u,v,nl;
 14 LL m,value,ans;
 15 struct node
 16 {
 17     int l,r,num;
 18 }tree[N<<2];
 19 void init(int i,int l,int r)
 20 {
 21     tree[i]=(node){l,r};
 22     if(l==r)
 23         return ;
 24     int mid=(l+r)>>1;
 25     init(i<<1,l,mid);
 26     init(i<<1|1,mid+1,r);
 27     return ;
 28 }
 29 void update(int i,int pos,int val)
 30 {
 31     if(tree[i].l==tree[i].r)
 32     {
 33         tree[i].num+=val;
 34         return ;
 35     }
 36     int mid=(tree[i].l+tree[i].r)>>1;
 37     if(mid>=pos)
 38         update(i<<1,pos,val);
 39     else
 40         update(i<<1|1,pos,val);
 41     tree[i].num+=val;
 42     return ;
 43 }
 44 LL query(int i,int l,int r)
 45 {
 46     if(tree[i].num==0)
 47         return -INF;
 48     if(tree[i].l>=l && tree[i].r<=r)
 49     {
 50         if(tree[i].l==tree[i].r)
 51             return val[tree[i].l];
 52         if(tree[i<<1|1].num)
 53             return query(i<<1|1,l,r);
 54         else return query(i<<1,l,r);
 55     }
 56     int mid=(tree[i].l+tree[i].r)>>1;
 57     LL ans=-INF;
 58     if(mid>=l)
 59         ans=max(ans,query(i<<1,l,r));
 60     if(mid<r)
 61         ans=max(ans,query(i<<1|1,l,r));
 62     return ans;
 63 }
 64 void dfs1(int u,int f)
 65 {
 66     cnum[u]=1;
 67     sum[u]=0;
 68     for(auto p:edge[u])
 69     {
 70         if(p.first!=f)
 71         {
 72             dfs1(p.first,u);
 73             cnum[u]+=cnum[p.first];
 74             sum[u]+=cnum[p.first]*p.second+sum[p.first];
 75         }
 76     }
 77     val[u]=sum[u];
 78     return ;
 79 }
 80 void dfs2(int u,int f)
 81 {
 82     ans=max(query(1,lower_bound(val+1,val+nl+1,sum[u])-val,upper_bound(val+1,val+nl+1,sum[u]+m)-1-val)-sum[u],ans);
 83     update(1,lower_bound(val+1,val+nl+1,sum[u])-val,1);
 84     for(auto p:edge[u])
 85         if(p.first!=f)
 86             dfs2(p.first,u);
 87     update(1,lower_bound(val+1,val+nl+1,sum[u])-val,-1);
 88     return ;
 89 }
 90 int main()
 91 {
 92     ios::sync_with_stdio(false);
 93     cin>>T;
 94     while(T--)
 95     {
 96         cin>>n>>m;
 97         for(int i=1;i<=n;i++)
 98             edge[i].clear();
 99         for(int i=2;i<=n;i++)
100         {
101             cin>>u>>v>>value;
102             edge[u].pb(mp(v,value));
103             edge[v].pb(mp(u,value));
104         }
105         ans=-1;
106         dfs1(1,1);
107         sort(val+1,val+n+1);
108         nl=unique(val+1,val+n+1)-val-1;
109         init(1,1,nl);
110         dfs2(1,1);
111         cout<<ans<<endl;
112     }
113     return 0;
114 }

View Code

题目描述

给一个1-base数组{a}，有N次操作，每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前，所有不包含无效位置的区间的权值的最大值。

输入描述:

第一行读入一个正整数(1 <= n <= 10⁵)

第二行读入n个正整数，第i个表示a[i](0<= a[i] <= 10⁹)

第三行读入n个正整数，第i个表示x[i]即第i次操作的位置，保证x[i]互不相同。

输出描述:

输出n行答案

示例1

输入

10
169 816 709 896 58 490 97 254 99 796 
4 2 3 10 5 6 1 8 9 7

输出

明显这个是分割区间的题，那么对于这种题我们就应该反着做，变成合并区间。求一个集合里任选的亦或最大值，那么首选就是线性基啦。那么从后往前做的话就相当于每次合并无效位置点和他左侧点所在区间（如果有的话）以及他右侧点所在区间（如果有的话）的线性基。我们可以用并查集来记录他们丛属哪个区间，以及区间的线性基。并拿这个合并后的线性基求最大值来更新当前亦或最大值。

  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x,0,sizeof(x))
  3 #define clr_1(x) memset(x,-1,sizeof(x))
  4 #define mod 1000000007
  5 #define LL long long
  6 #define INF 0x3f3f3f3f
  7 #define pb(x) push_back(x)
  8 #define mp(x,y) make_pair(x,y)
  9 using namespace std;
 10 const int N=1e5+10;
 11 const int type=32;
 12 int fa[N];
 13 int Find(int x)
 14 {
 15     if(fa[x]!=x)
 16         fa[x]=Find(fa[x]);
 17     return fa[x];
 18 }
 19 LL liner[N][type],ans[N],rans,p;
 20 int n,a[N],x[N],vis[N];
 21 int t;
 22 void Union(int x,int y)
 23 {
 24     int xx=Find(x);
 25     int yy=Find(y);
 26     LL p;
 27     for(int i=type-1;i>=0;i--)
 28     {
 29         if(liner[xx][i])
 30         {
 31             p=liner[xx][i];
 32             for(int j=type-1;j>=0;j--)
 33             {
 34                 if(p>>j)
 35                 {
 36                     if(liner[yy][j])
 37                         p^=liner[yy][j];
 38                     else
 39                     {
 40                         liner[yy][j]=p;
 41                         break;
 42                     }
 43                 }
 44             }
 45         }
 46     }
 47     fa[xx]=yy;
 48     return ;
 49 }
 50 void init(int n)
 51 {
 52     clr(liner);
 53     LL p;
 54     for(int i=1;i<=n;i++)
 55     {
 56         fa[i]=i;
 57         vis[i]=0;
 58         p=(LL)a[i];
 59         for(int j=type-1;j>=0;j--)
 60         {
 61             if(p>>j)
 62             {
 63                 if(!liner[i][j])
 64                 {
 65                     liner[i][j]=p;
 66                     break;
 67                 }
 68                 else
 69                     p=p^liner[i][j];
 70             }
 71         }
 72     }
 73     return ;
 74 }
 75 int main()
 76 {
 77     scanf("%d",&n);
 78     for(int i=1;i<=n;i++)
 79         scanf("%d",a+i);
 80     for(int i=1;i<=n;i++)
 81         scanf("%d",x+i);
 82     init(n);
 83     rans=0;
 84     for(int i=n;i>=1;i--)
 85     {
 86         vis[x[i]]=1;
 87         if(vis[x[i]-1])
 88             Union(x[i]-1,x[i]);
 89         if(vis[x[i]+1])
 90             Union(x[i]+1,x[i]);
 91         t=Find(x[i]);
 92         p=0;
 93         for(int j=31;j>=0;j--)
 94             if(liner[t][j])
 95                 p=max(p^liner[t][j],p);
 96         rans=max(rans,p);
 97         ans[i]=rans;
 98     }
 99     for(int i=1;i<=n;i++)
100         printf("%lld
",ans[i]);
101     return 0;
102 }

View Code