Codeforces Round #746 (Div. 2)

A.贪心

很简单，不能连续的放同一个

那么我肯定是最大攻击力和次大攻击力的武器交替使用

#include
using namespace std;
const int maxn = 2e5+100;
inline int read(){
    char c=getchar();
    int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
void write(int num)
{
	if (num/10)write(num/10);
	putchar('0'+num%10);
}
int n,h;
int num1,num2,num;
int main()
{
	int T=read();
	while (T--)
	{
		n=read();h=read();
		num1=read();num2=read();
		if (num1>num2)swap(num1,num2);
		for (int i=2;inum1)num1=num;
			if (num1>num2)swap(num1,num2);
		}
		write(h/(num1+num2)*2+(h%(num1+num2)+num2-1)/num2);puts("");
	}
}

B.思维

短暂的思考，我们注意到数组中可能存在一些无法动弹的数字

即，对于一些索引 i i i， i − 1 < x , n − i < x i-1

因此这些索引一开始就应当站在正确的位置上

而对于其他可以动弹的索引，可以利用两端点，自由交换

#include
using namespace std;
const int maxn = 2e5+100;
int a[maxn],b[maxn];
int n,x;
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		cin>>n>>x;
		for (int i=1;i<=n;++i)cin>>a[i],b[i]=a[i];
		sort(b+1,b+1+n);
		string ans = "YESn";
		for (int i=1;i<=n;++i)if (i-1 
C.思维 
很好的思维题 
考虑
    
     
      
       
        ⊕
       
       
        
       
      
      
       oplus
      
     
    ⊕操作的特性 
当整棵树的
     
      
       
        
         ⊕
        
       
       
        oplus
       
      
     ⊕和为
     
      
       
        
         0
        
       
       
        0
       
      
     0，那么随便断掉一个叶子节点即可满足条件
当中整棵树的
     
      
       
        
         ⊕
        
       
       
        oplus
       
      
     ⊕和不为
     
      
       
        
         0
        
       
       
        0
       
      
     0，记为
     
      
       
        
         t
        
        
         a
        
        
         r
        
       
       
        tar
       
      
     tar，断边后的每一个连通分量
     
      
       
        
         ⊕
        
       
       
        oplus
       
      
     ⊕和都为
     
      
       
        
         t
        
        
         a
        
        
         r
        
       
       
        tar
       
      
     tar 
考虑第二种情况，如果选取了合适的节点作为根： 
 
被红框圈起来的子树，其
    
     
      
       
        ⊕
       
      
      
       oplus
      
     
    ⊕和为
    
     
      
       
        t
       
       
        a
       
       
        r
       
      
      
       tar
      
     
    tar 
我们可以通过断
    
     
      
       
        3
       
       
        −
       
       
        7
       
       
        ,
       
       
        2
       
       
        −
       
       
        5
       
      
      
       3-7,2-5
      
     
    3−7,2−5两条边实现目标 
最多使用两次断边 
但是，考虑到我么每次都默认以
    
     
      
       
        1
       
      
      
       1
      
     
    1为根，可能出现这种情况： 
 
如图，
    
     
      
       
        ⊕
       
      
      
       oplus
      
     
    ⊕和为
    
     
      
       
        t
       
       
        a
       
       
        r
       
      
      
       tar
      
     
    tar的子树跨越了根节点
    
     
      
       
        1
       
      
      
       1
      
     
    1 
我们观察到，满足这种情况下，节点
    
     
      
       
        7
       
      
      
       7
      
     
    7 
    
     
      
       
        ⊕
       
      
      
       oplus
      
     
    ⊕和为
    
     
      
       
        0
       
      
      
       0
      
     
    0，且节点
    
     
      
       
        7
       
      
      
       7
      
     
    7含有一棵子树
    
     
      
       
        ⊕
       
      
      
       oplus
      
     
    ⊕和为
    
     
      
       
        t
       
       
        a
       
       
        r
       
      
      
       tar
      
     
    tar 
因此进行
    
     
      
       
        d
       
       
        f
       
       
        s
       
       
        (
       
       
        u
       
       
        )
       
      
      
       dfs(u)
      
     
    dfs(u)，计算每个节点的
    
     
      
       
        ⊕
       
      
      
       oplus
      
     
    ⊕和
    
     
      
       
        x
       
       
        o
       
       
        r
       
       
        [
       
       
        u
       
       
        ]
       
      
      
       xor[u]
      
     
    xor[u]，同时判断以该节点为根的子树中是否存在子树
    
     
      
       
        ⊕
       
      
      
       oplus
      
     
    ⊕和为
    
     
      
       
        t
       
       
        a
       
       
        r
       
      
      
       tar
      
     
    tar 
    
     
      
       
        h
       
       
        a
       
       
        s
       
       
        [
       
       
        u
       
       
        ]
       
      
      
       has[u]
      
     
    has[u] 
如果存在两个儿子
    
     
      
       
        
         v
        
        
         1
        
       
       
        ,
       
       
        
         v
        
        
         2
        
       
      
      
       v_1,v_2
      
     
    v1,v2，
    
     
      
       
        h
       
       
        a
       
       
        s
       
       
        [
       
       
        
         v
        
        
         1
        
       
       
        ]
       
       
        =
       
       
        =
       
       
        h
       
       
        a
       
       
        s
       
       
        [
       
       
        
         v
        
        
         2
        
       
       
        ]
       
       
        =
       
       
        =
       
       
        1
       
      
      
       has[v_1]==has[v_2]==1
      
     
    has[v1]==has[v2]==1 那么
    
     
      
       
        Y
       
       
        E
       
       
        S
       
      
      
       YES
      
     
    YES 
如果
    
     
      
       
        x
       
       
        o
       
       
        [
       
       
        u
       
       
        ]
       
       
        =
       
       
        =
       
       
        0
       
      
      
       xo[u]==0
      
     
    xo[u]==0且存在儿子
    
     
      
       
        v
       
      
      
       v
      
     
    v使得
    
     
      
       
        h
       
       
        a
       
       
        s
       
       
        [
       
       
        v
       
       
        ]
       
       
        =
       
       
        =
       
       
        1
       
      
      
       has[v]==1
      
     
    has[v]==1同样
    
     
      
       
        Y
       
       
        E
       
       
        S
       
      
      
       YES
      
     
    YES 
#include
using namespace std;
const int maxn = 2e5+100;
vector G[maxn];
int tar,a[maxn];
bool has[maxn];
int xo[maxn];
int n,k;
bool dfs(int u,int fa)
{
	xo[u]=a[u];has[u]=0;
	int cnt=0;
	for (int v:G[u])if (v!=fa)
	{
		if (dfs(v,u))return true;
		xo[u]^=xo[v];
		if (has[v])++cnt;
		if (xo[v]==0&&has[v])return true;
	}
	if (xo[u]==tar)has[u]=1;
	if (cnt>0)has[u]=1;
	if (cnt>=2)return true;
	return false;
}
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		cin>>n>>k;tar=0;
		for (int i=1;i<=n;++i)G[i].clear();
		for (int i=1;i<=n;++i)cin>>a[i],tar^=a[i];
		for (int i=1,u,v;i>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		if (tar==0)cout<<"YESn";
		else
		{
			if (k>=3&&dfs(1,0))cout<<"YESn";
			else cout<<"NOn";
		}
	}
}
 
D.思维+二分 
稍微思考一下，其实题目要求我们找到最大的那一条边 
每次的询问也是返回所有点路径上的最大边的权值 
既然如此，我们自然想要对边进行二分 
观察数据范围，查询最多
    
     
      
       
        12
       
      
      
       12
      
     
    12次，一共
    
     
      
       
        1
       
       
        e
       
       
        3
       
      
      
       1e3
      
     
    1e3条边，很合理 
但是，这时出现了一个问题。我们该如何二分边呢？ 
不能简单的将所有便存储起来，然后每次二分一半 
以样例为为例，会出现这种现象： 
 
此刻我们有边
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        2
       
       
        )
       
       
        ,
       
       
        (
       
       
        1
       
       
        ,
       
       
        5
       
       
        )
       
       
        ,
       
       
        (
       
       
        2
       
       
        ,
       
       
        3
       
       
        )
       
       
        ,
       
       
        (
       
       
        2
       
       
        ,
       
       
        4
       
       
        )
       
       
        ,
       
       
        (
       
       
        5
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (1,2),(1,5),(2,3),(2,4),(5,6)
      
     
    (1,2),(1,5),(2,3),(2,4),(5,6) 
分一半为
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        2
       
       
        )
       
       
        ,
       
       
        (
       
       
        1
       
       
        ,
       
       
        5
       
       
        )
       
       
        ,
       
       
        (
       
       
        2
       
       
        ,
       
       
        3
       
       
        )
       
      
      
       (1,2),(1,5),(2,3)
      
     
    (1,2),(1,5),(2,3)和
    
     
      
       
        (
       
       
        2
       
       
        ,
       
       
        4
       
       
        )
       
       
        ,
       
       
        (
       
       
        5
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (2,4),(5,6)
      
     
    (2,4),(5,6) 
观察
    
     
      
       
        (
       
       
        2
       
       
        ,
       
       
        4
       
       
        )
       
       
        ,
       
       
        (
       
       
        5
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (2,4),(5,6)
      
     
    (2,4),(5,6)我们发现这些边有
    
     
      
       
        4
       
      
      
       4
      
     
    4个点，如果我们查询
    
     
      
       
        2
       
       
        ,
       
       
        4
       
       
        ,
       
       
        5
       
       
        ,
       
       
        6
       
      
      
       2,4,5,6
      
     
    2,4,5,6的话 
那么实际上返回的是
    
     
      
       
        (
       
       
        2
       
       
        ,
       
       
        4
       
       
        )
       
       
        ,
       
       
        (
       
       
        2
       
       
        ,
       
       
        1
       
       
        )
       
       
        ,
       
       
        (
       
       
        1
       
       
        ,
       
       
        5
       
       
        )
       
       
        ,
       
       
        (
       
       
        5
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (2,4),(2,1),(1,5),(5,6)
      
     
    (2,4),(2,1),(1,5),(5,6)中最大的值 
与我们想法不一样 
因此，这里的二分是有讲究的 
我们二分出来的边，这些边要能够造成一棵树！ 
即将边中出现的所有点完全连通 
只有这样才能避免出现上述的情况 
这里给出一种比较简单实现的方案 
我们按照
    
     
      
       
        d
       
       
        f
       
       
        s
       
      
      
       dfs
      
     
    dfs的顺序添加边，有所不同的是回溯的边也要添加 
可能会有边被重复添加了，但是可以保证每一次二分的时候，两边的边都可以联通 
#include
using namespace std;
const int maxn = 1100;
array res;
int ans;
int n;
int query(vector>& es)
{
	set se;
	for (array ar:es)se.insert(ar[0]),se.insert(ar[1]);
	cout<<"? "<>ret;
	cout.flush();
	return ret;
}
void solve(vector> es)
{
	if (es.size()==1)
	{
		res = es[0];
		return;
	}
	vector> nxt;
	while (es.size()>nxt.size())
	{
		nxt.push_back(es.back());
		es.pop_back();
	}
	if (query(es)==ans)solve(es);
	else solve(nxt);
}
vector> edges;
vector G[maxn];
void dfs(int u,int fa)
{
	for (int v:G[u])if (v!=fa)
	{
		edges.push_back({u,v});
		dfs(v,u);
		edges.push_back({v,u});
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for (int i=1,u,v;i>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	ans = query(edges);
	solve(edges);
	cout<<"! "< 
E.思维 +前缀和 
何时
    
     
      
       
        
         a
        
        
         l
        
       
       
        &
       
       
        
         a
        
        
         
          l
         
         
          +
         
         
          1
         
        
       
       
        &
       
       
        
         a
        
        
         
          l
         
         
          +
         
         
          2
         
        
       
       
        &
       
       
        ,
       
       
        …
       
       
        ,
       
       
        &
       
       
        
         a
        
        
         r
        
       
       
        >
       
       
        
         a
        
        
         l
        
       
       
        ⊕
       
       
        
         a
        
        
         
          l
         
         
          +
         
         
          1
         
        
       
       
        ⊕
       
       
        
         a
        
        
         
          l
         
         
          +
         
         
          2
         
        
       
       
        ⊕
       
       
        ,
       
       
        …
       
       
        ,
       
       
        ⊕
       
       
        
         a
        
        
         r
        
       
      
      
       a_l & a_{l+1} & a_{l+2} & , dots,& a_r>a_l oplus a_{l+1}oplus a_{l+2}oplus,dots,oplus a_r
      
     
    al&al+1&al+2&,…,&ar>al⊕al+1⊕al+2⊕,…,⊕ar 
位运算的问题一般都是按位看，从高到低看 
我们注意到，倘若
    
     
      
       
        A
       
       
        N
       
       
        D
       
      
      
       AND
      
     
    AND和与
    
     
      
       
        X
       
       
        O
       
       
        R
       
      
      
       XOR
      
     
    XOR和在前
    
     
      
       
        k
       
       
        −
       
       
        1
       
      
      
       k-1
      
     
    k−1位都相同，在
    
     
      
       
        k
       
       
        −
       
       
        1
       
      
      
       k-1
      
     
    k−1位出现不同 
此时
    
     
      
       
        A
       
       
        N
       
       
        D
       
      
      
       AND
      
     
    AND在第
    
     
      
       
        k
       
      
      
       k
      
     
    k位为
    
     
      
       
        1
       
      
      
       1
      
     
    1，
    
     
      
       
        X
       
       
        O
       
       
        R
       
      
      
       XOR
      
     
    XOR为
    
     
      
       
        0
       
      
      
       0
      
     
    0 (从高位向地位看) 
首先考虑
    
     
      
       
        A
       
       
        N
       
       
        D
       
      
      
       AND
      
     
    AND在第
    
     
      
       
        k
       
      
      
       k
      
     
    k位为
    
     
      
       
        1
       
      
      
       1
      
     
    1，那么
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]上所有的数第
    
     
      
       
        k
       
      
      
       k
      
     
    k位都为
    
     
      
       
        1
       
      
      
       1
      
     
    1 
再考虑，
    
     
      
       
        X
       
       
        O
       
       
        R
       
      
      
       XOR
      
     
    XOR第
    
     
      
       
        k
       
      
      
       k
      
     
    k位为
    
     
      
       
        0
       
      
      
       0
      
     
    0，那么
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]上第
    
     
      
       
        k
       
      
      
       k
      
     
    k位为
    
     
      
       
        1
       
      
      
       1
      
     
    1的数有偶数个 
综上，我们得出结论
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]的长度一定为偶数，且前
    
     
      
       
        k
       
       
        −
       
       
        1
       
      
      
       k-1
      
     
    k−1位
    
     
      
       
        A
       
       
        N
       
       
        D
       
      
      
       AND
      
     
    AND与
    
     
      
       
        X
       
       
        O
       
       
        R
       
      
      
       XOR
      
     
    XOR都为
    
     
      
       
        0
       
      
      
       0
      
     
    0 
预处理前缀亦或和数组
    
     
      
       
        p
       
       
        r
       
       
        e
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       pre[i]
      
     
    pre[i] 
我们枚举
    
     
      
       
        k
       
      
      
       k
      
     
    k，从
    
     
      
       
        0
       
      
      
       0
      
     
    0到
    
     
      
       
        21
       
      
      
       21
      
     
    21 
枚举
    
     
      
       
        r
       
      
      
       r
      
     
    r，找最远的符合条件的
    
     
      
       
        l
       
      
      
       l
      
     
    l 
首先，
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]为偶数长度这一目标很容易实现 
但是，如何保证前
    
     
      
       
        k
       
       
        −
       
       
        1
       
      
      
       k-1
      
     
    k−1位都是
    
     
      
       
        0
       
      
      
       0
      
     
    0呢？ 
利用前缀亦或和数组
    
     
      
       
        p
       
       
        r
       
       
        e
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       pre[i]
      
     
    pre[i] 
在
    
     
      
       
        p
       
       
        r
       
       
        e
       
       
        [
       
       
        l
       
       
        ]
       
      
      
       pre[l]
      
     
    pre[l]前
    
     
      
       
        k
       
       
        −
       
       
        1
       
      
      
       k-1
      
     
    k−1与
    
     
      
       
        p
       
       
        r
       
       
        e
       
       
        [
       
       
        r
       
       
        ]
       
      
      
       pre[r]
      
     
    pre[r]前
    
     
      
       
        k
       
       
        −
       
       
        1
       
      
      
       k-1
      
     
    k−1位相同的集合里搜寻 
同时要满足
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]第
    
     
      
       
        k
       
      
      
       k
      
     
    k位都是
    
     
      
       
        1
       
      
      
       1
      
     
    1，这个可以利用双指针实现 
#include
using namespace std;
list mp1[1<<21],mp2[1<<21];
int pre[1<<21];
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for (int i=1;i<=n;++i)cin>>pre[i],pre[i]^=pre[i-1];
	int ans = 0;
	for (int k=0;k<=21;++k)
	{
		mp2[0].push_back(0);
		int l = 1;
		for (int i=1;i<=n;++i)
		{
			if (!((pre[i]^pre[i-1])&1))l=i+1;
			int id = pre[i];
			if (i&1)
			{
				while (!mp1[id].empty()&&mp1[id].front()+1>=1;
		}mp1[0].clear();mp2[0].clear();
	}cout<

Codeforces Round #746 (Div. 2)

C/C++/C#相关栏目本月热门文章