#ACM训练联盟周赛第二场
Ａ
格式化输出
B. Zeratul与塔防游戏
先预处理出来覆盖每一个点的区间的最远右端点是多少，然后二分答案，并从1…m扫，如果不满足就修改从i 到nxt[i]到满足
B.cpp
C 凉菜鸡不会线段树
莫队+字典树，黄学长上来就秒了，tql
莫队+trie树
怎么做呢？
首先将异或sum改为前缀，这样就是求 L,R 之间的数和 a[L−1],a[R−1]进行异或的值大于K的个数，利用trie树在异或上的应用，可以用trie树节点的值代表数的个数
莫队暴力修改每一个点的值的时候，查询这个点和多少个点的异或值>K,只需要统计符合条件的trie树子树的数的个数就ok了，当k的第i位为0的时候，这个时候x异或相反的值得到1，所以需要c^1 的子树的节点个数加上，然后到c子树去，当k的第i为1的时候，我们必须走到同样为1的节点上去，才能保证比这个大，所以这个时候是 c⊕1
这两种情况都是到 c⊕K>>i节点
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int block,n,m,tot = 1,K;
int a[maxn];
const int M = maxn*16;
int v[M],ch[M][2];
typedef long long LL;
LL ans[maxn];
LL Ans;
struct Qu{
int l,r,id;
bool operator <(const Qu &a){
if(l/block == a.l /block)
return r < a.r;
else
return l/block < a.l /block;
}
} q[maxn];
void Insert(int x,int p){
int u = 1;
for(int i = 16;i >= 0; --i){
int t = x>>i&1;
// cout<<t<<endl;
if(!ch[u][t])
ch[u][t] = ++tot;
// v[ch[u][t]] += p;
// cout<<u<<" "<<ch[u][t]<<endl;
u = ch[u][t];
v[u] += p;
// cout<<v[1]<<endl;
// cout<<u<<endl;
// cout<<tot<<endl;
// cout<<v[u]<<endl;
}
}
int Query(int x){
int u = 1;
int cnt = 0;
for(int i = 16;i >= 0; --i){
int t = x>>i&1;
int t2 = K>>i&1;
if(t2==0)
cnt += v[ch[u][t^1]];
u = ch[u][t^t2];
}
// cout<<cnt<<endl;
return cnt;
}
void Update(int x,int p){
// cout<<p<<endl;
// cout<<p*Query(x)<<endl;
Ans += p*Query(x);
Insert(x,p);
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>K;
for(int i = 1;i <= n; ++i)
cin>>a[i],a[i] ^= a[i-1];
// DEBUG;
// cout<<a[n]<<endl;
for(int i = 1;i <= m; ++i)
cin>>q[i].l>>q[i].r,q[i].id = i,q[i].l--;
block = sqrt(n);
sort(q+1,q+m+1);
// for(int i = 1;i <= m; ++i)
// cout<<q[i].l<<" "<<q[i].r<<endl;
// Insert(0,1);
for(int i = 1,L = 1,R = 0;i <= m; ++i){
while(L < q[i].l) Update(a[L++],-1);
while(L > q[i].l) Update(a[--L],1);
while(R > q[i].r) Update(a[R--],-1);
while(R < q[i].r) Update(a[++R],1);
ans[q[i].id] = Ans;
}
for(int i = 1;i <= m; ++i)
cout<<ans[i]<<"\n";
return 0;
}
D Dungeon♂Master
组合数学tql，看不出来
大力分类讨论
我们发现去掉的情况就只有标出的这种，除了左下角那个是两个转移的，其他都是一个，把这些情况减去就ok了！
const int maxn = 1e6+10;
LL fac[maxn],invfac[maxn];
void init(int n){
fac[0] = 1;
invfac[0] =1;
for(int i = 1;i <= n; ++i)
fac[i] = fac[i-1]*i%mod;
invfac[n] = qpow(fac[n],mod-2);
for(int i = n-1;i >=1;--i)
invfac[i] = invfac[i+1]*(i+1)%mod;
}
LL C(LL n,LL m){
return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
LL cal(LL x,LL y,LL xx,LL yy){
return C(xx-x+yy-y,xx-x);
}
int main(void)
{
init(maxn-1);
// cout<<fac[10]*invfac[10]%mod<<endl;
// cout<<cal(1,1,)
LL n;cin>>n;
LL ans = 0;
for(int i = 1;i <= n; ++i){
ans -= cal(1,1,i,3*n)*cal(i,3*n+1,4*n,4*n)%mod;
ans %= mod;
}
for(int i = 2*n+1;i <= 3*n; ++i){
ans -= cal(1,1,i,n)*cal(i,n+1,4*n,4*n)%mod;
ans %= mod;
}
for(int j = n+1;j <= 2*n; ++j){
ans -= cal(1,1,2*n,j)*cal(2*n+1,j,4*n,4*n)%mod;
ans %= mod;
}
ans = (ans+cal(1,1,4*n,4*n)+mod)%mod;
cout<<ans<<endl;
return 0;
}
E 暖气管道
双连通分量+dp
先通过求边-双联通分量缩点，变成一棵树，之后对于每一个节点求子书里面的最大值，用总的减去即可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct Edge
{
int no,v,next,w; //no：边的编号
}edges[maxn];
int n,m,ebcnum; //节点数目，无向边的数目，边_双连通分量的数目
int e,head[maxn];
int pre[maxn]; //第一次访问的时间戳
int dfs_clock; //时间戳
int isbridge[maxn]; //标记边是否为桥
vector<int> ebc[maxn]; //边_双连通分量
void addedges(int num,int u,int v) //加边
{
edges[e].no = num;
edges[e].v = v;
// edges[e].w = w;
edges[e].next = head[u];
head[u] = e++;
edges[e].no = num++;
edges[e].v = u;
// edges[e].w = w;
edges[e].next = head[v];
head[v] = e++;
}
int dfs_findbridge(int u,int fa) //找出所有的桥
{
int lowu = pre[u] = ++dfs_clock;
for(int i=head[u];i!=-1;i=edges[i].next)
{
int v = edges[i].v;
if(!pre[v])
{
int lowv = dfs_findbridge(v,u);
lowu = min(lowu,lowv);
if(lowv > pre[u])
{
isbridge[edges[i].no] = 1; //桥
}
}
else if(pre[v] < pre[u] && v != fa)
{
lowu = min(lowu,pre[v]);
}
}
return lowu;
}
void dfs_coutbridge(int u,int fa) //保存边_双连通分量的信息
{
ebc[ebcnum].push_back(u);
pre[u] = ++dfs_clock;
for(int i=head[u];i!=-1;i=edges[i].next)
{
int v = edges[i].v;
if(!isbridge[edges[i].no] && !pre[v]) dfs_coutbridge(v,u);
}
}
void init()
{
memset(pre,0,sizeof(pre));
memset(isbridge,0,sizeof(isbridge));
memset(head,-1,sizeof(head));
e = 0; ebcnum = 0;
}
vector<int> G[maxn];
bool vis[maxn];
int F[maxn];
typedef long long LL;
LL ans[maxn];
LL sum[maxn];
int v1[maxn];
int val[maxn];
LL S;
void FindEdge(int n) //保存边_双连通分量的信息
{
// vis[u] = true;
// int x = F[u];
for(int u = 1;u <= n; ++u){
int x = F[u];
for(int i=head[u];i!=-1;i=edges[i].next)
{
int v = edges[i].v;
int y = F[v];
if(x == y) continue;
G[x].push_back(y);
G[y].push_back(x);
}
}
}
void Dfs(int u,int fa){
vis[u] =true;
sum[u] = val[u];
LL Max = 0;
for(auto c: G[u]){
if(vis[c]) continue;
Dfs(c,u);
Max = max(Max,sum[c]);
sum[u] += sum[c];
}
if(u != 1)
Max = max(Max,S-sum[u]);
ans[u] = Max;
}
int main()
{
int u,v;
// freopen("in.txt","r",stdin);
// while(scanf("%d%d",&n,&m)!=EOF)
// {
cin>>n>>m;
init();
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
addedges(i,u,v);
}
S = 0;
for(int i = 1;i <= n; ++i)
scanf("%d",&v1[i]),S += v1[i];
dfs_findbridge(1,-1);
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
{
if(!pre[i])
{
ebc[ebcnum].clear();
dfs_coutbridge(i,-1);
ebcnum++;
}
}
// cout<<ebcnum<<endl;
for(int i=0;i<ebcnum;i++)
{
for(int j=0;j<ebc[i].size();j++)
F[ebc[i][j]] = i+1,val[i+1] += v1[ebc[i][j]];
// cout<<ebc[i][j]<<" ";
// cout<<endl;
}
FindEdge(n);
memset(vis,0,sizeof(vis));
Dfs(1,-1);
// }
int T;cin>>T;
while(T--){
int a;scanf("%d",&a);
printf("%lld\n",S-ans[F[a]]);
}
return 0;
}
F. 题面很短的简单题
分情况讨论即可
G. 这是一道数学题
HDU3307
欧拉函数的应用 a^phi(m) % m = 1 要求 a 与m互质，否则不存在
最小的一定是a的因子
I. Not XOR but OR
O(n3) 可过
正解如下
I.设原数组为A数组。很容易想到dp[i][j]表示前i个数分成k组的最大值 ，那么问题在于怎么进行状态转移。
显然dp[i][j]=max(dp[t][j-1]+(A[t+1]|A[t+2]…|A[i]))。但这样转移时O(n)的，总复杂度就变成了n^3。
接着我们可以发现随着dp[i][j]会随着i的值变大（即dp[i][j]>=dp[i-1][j]）而(A[t+1]|A[t+2]…|A[i])的值只会变换不超过30次。所以我们取30个变换点进行DP复杂度就变成O(31n^2)了
int n,k;
const int maxn = 1000+100;
#define int long long
int a[maxn];
int dp[maxn][maxn]; // 代表前i个，j个分组的最大值
int sum[maxn][maxn];
int32_t main(void)
{
int t;cin>>t;
while(t--){
me(a);
me(dp);
me(sum);
int n,k;cin>>n>>k;
for(int i = 1;i <= n; ++i)
scanf("%lld",&a[i]);
for(int i = 1;i <= n; ++i){
sum[i][i] = a[i];
for(int j = i+1;j <= n; ++j)
sum[i][j] = sum[i][j-1]|a[j];
}
// cout<<sum[1][2]<<endl;
for(int i = 1;i <= n; ++i){
vector<int> vec;
vec.push_back(0);
LL s = 0;
for(int l = i;l >= 0; --l){
if((s | a[l]) != s)
vec.push_back(l);
s |= a[l];
}
for(int j = 1;j <= k; ++j){
dp[i][j] = 0;
for(auto l:vec){
if(l >= j)
dp[i][j] = max(dp[l-1][j-1]+(sum[l][i]),dp[i][j]);
}
}
}
cout<<dp[n][k]<<endl;
}
return 0;
}
J. 合并石堆
注意可以任意选择i,j 只是加了限制k次，相当于一个k叉树，按从大到小从根到底部挨个填，深度就是用的次数
const int maxn = 1e5+10;
LL a[maxn];
LL sum[maxn];
LL s[maxn];
int main(void)
{
// freopen("input.txt","r",stdin);
// freopen("output1.txt","w+",stdout);
// IOS;
int n;cin>>n;
rep(i,1,n+1) scanf("%lld",&a[i]);//,sum[i] = sum[i-1]+a[i];
sort(a+1,a+n+1,greater<LL>());
rep(i,1,n+1) sum[i] = sum[i-1]+a[i],sum[i]%=mod;
int q;cin>>q;
bool flag = true;
while(q--){
int k;scanf("%d",&k);
if(flag) flag = false;
else
putchar(' ');
if(s[k])
{
printf("%lld",s[k]);
continue;
}
LL ans = 0;
LL pre = 1;
LL t = 0;
for(LL i = 1,p = 1;i <= n; p *= k,i += p,t++){
// cout<<i<<endl;
if(i!=1)
ans = (ans+(sum[i]-sum[pre])*t%mod)%mod;
pre = i;
}
// cout<<pre<<endl;
// cout<<ans<<endl;
if(pre != n)
ans = (ans+(sum[n]-sum[pre])*t%mod)%mod;
printf("%lld",ans);
s[k] = ans;
}
return 0;
}
K. A.CM真好玩！我要充钱
思维题
L. Mario与Luigi的组合游戏
题解：
显然m是偶数的话偶数SG值除了SG[2]是2其他都是1。
如果m是奇数因为只有拿走一个棋子和偶数拆成m堆两种情况， 前几个打下表，后面的偶数可以logn判断，奇数显然是0. 直接暴力求SG值复杂度O(nlogn)刚刚好
组合博弈的典型应用，会SG函数和找规律即可
京公网安备 11010502036488号