Codeforces Round #779 (Div. 2)
admin
|
|
253
|
Codeforces

1436 字
|
20 分钟

Codeforces Round #779 (Div. 2)

C. Shinju and the Lost Permutation「思维 」

题目描述：

对于全排列 [公式] ，我们有以下内容。

  • [公式] 的前缀最大值 [公式] ， [公式]
  • 一个操作 “右移” ， 比如 [公式] 右移会变成 [公式] （把最后一个数放到前面

现在给定一个长度为 [公式] 的数组 [公式] ,问是否存在一个全排列 [公式] ，满足:

对于所有的 [公式]

[公式] 经过 [公式] 次右移后，其前缀最大值 [公式] 中不同的数有 [公式] 个。

只输出YES或者NO

思路：

显然，cr[i]中有且仅有一个1，而且1出现的位置应该是最大值的位置，因为进行了i次轮转后，移动到最开头，此时前缀最大值的不同的数的数量是1，这只可能是最大值出现在了第一顺位的情况

所以我们可以先判断1的数量是不是等于1

因为轮转x和轮转x + n次是一样的，所以我们可以把c[i] = 1的位置的前面的数字平移到n后面去

每次轮转改变c[i]的时候,有两种情况

  • 变大，只可能+1，因为只可能将一个小于当前第一个数字的数字轮转到第一个数前，才会使得c[i]变大
  • 变小，可以变小成任意值

所以我们只需要判断相邻两个数字的差就可以

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];tr[i + n] = tr[i];
    }
    if(count(tr + 1, tr + 1 + n, 1) != 1){
        cout << "NO\n";
        return;
    }
    vector<int>v;
    for(int i = 1; i <= n; ++i){
        if(tr[i] == 1){
            for(int j = i; j <= i + n - 1; ++j)v.push_back(tr[j]);
            break;
        }
    }
    for(int i = 1; i < v.size(); ++i){
        if(v[i] - v[i - 1] > 1){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

D1. 388535 (Easy Version)

题目描述：

给定一个l = 0,r，数组a[i]是数值从l到r的一个全排列

然后选择了一个数x,定义数组b[i] = a[i] ^ x

给出b[i]数组，问x是多少

我的思路：

因为l=0，而0异或任意一个数字都得到那个数字，所以答案肯定在a[i]中，所以我们只需要想一个check的方法就行

我的方法是：

  • 开一个num[20]数组来统计[0, r]中的数转换成二进制后每一位的1的数量

  • 开一个cnt[20]数组来统计[b[1], b[r - l + 1]]中数字转换成二进制后的每一位的1的数量

  • 判断x是否合法的方法是：

    • 如果x当前位是1，则判断num[i] = n - cnt[i]，

      因为如果是1，那所有位异或1后，就会变成和自身相反的数，也就是异或前1的数量应该等于异或后0的数量，异或后0的数量其实等于n减去异或后1的数量，也就是n - cnt[i]

    • 如果x当前位是0，则判断num[i] = cnt[i]

      因为如果是0，不管是0还是1，异或0后都不变，也就是异或前后1的数量不变，也就是nunm[i] = cnt[i]

所以枚举[0, r]中的每一个数去check即可

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int l, r;
int tr[MAX];
int num[30];
int cnt[30];

bool check(int x){
    for(int i = 0; i <= 17; ++i){
        if(x & (1 << i)){
            if(n - cnt[i] != num[i])return false;
        }
        else{
            if(cnt[i] != num[i])return false;
        }
    }
    return true;
}

void work(){
    cin >> l >> r;
    n = r - l + 1;
    mem(num, 0);mem(cnt, 0);
    for(int i = 1; i < n; ++i){
        for(int j = 0; j <= 17 && (1 << j) <= i; ++j){
            if(i & (1 << j))++num[j];
        }
    }
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        for(int j = 0; j <= 17 && (1 << j) <= tr[i]; ++j){
            if(tr[i] & (1 << j))++cnt[j];
        }
    }
    for(int i = 1; i <= n; ++i){
        if(check(tr[i])){
            cout << tr[i] << endl;
            return;
        }
    }
    
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

官方思路：

观察一下0到7个数的二进制情况

  • 000
  • 001
  • 010
  • 011
  • 100
  • 101
  • 110
  • 111

对于每一位来说，前缀中0的数量要大于等于1的数量

所以我们可以统计cnt[i]表示a数组中数字的第i位为1的数量，如果哪一位的cnt[i] > n - cnt[i]，就说明x的这一位是1（因为异或1以后数量就反转过来了，使的大的那个数一定是0的）

（居然没我的思路跑的快，真怪

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int l, r;
int tr[20];

void work(){
    cin >> l >> r;
    n = r - l + 1;
    mem(tr, 0);
    for(int i = 1; i <= n; ++i){
        cin >> k;
        for(int j = 17; j >= 0; --j){
            if(k & (1 << j))++tr[j];
        }
    }
    int ans = 0;
    for(int i = 17; i >= 0; --i){
        if(tr[i] > n - tr[i])ans |= (1 << i);
    }
    cout << ans << endl;
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

D2. 388535 (Hard Version)「字典树」

题目描述：

和easy版本一样，只不过l>=0了

思路：

原数组a[i]:

异或x后：

我们可以用一个01字典树来维护

字典树上插入的数是b[i],我们可以枚举x,来求异或最大值和异或最小值，拿来和r, l进行比较，只有都想等的时候就说明符合要求

但是x的范围是[0, 217 – 1],暴力枚举会T

这时候用一个简单的异或小知识:(x^y)^y = x，我们只需要计算b[i]^l即可，因为b[i] = a[i]^x,其中一定有一个是l ^ x，我们再异或一个l,就会只剩下x

所以我们需要进行r - l + 1次01字典树找异或最大值和异或最小值，进行判断

初始化很重要，暴力初始化会TLE

插入的时候进行初始化，注意是那个地方是tot不是root，妈的昨晚debug了一个多小时才找出来

void init()
{
 tr[0][0] = tr[0][1] = 0;
 tot = 1;
}
void insert(int x){//插入的过程也有一个地方需要初始化
 int root = 0;
 for(int i = 17; i >= 0; --i){
     int id = ((x >> i) & 1);
     if(!tr[root][id]){
         tr[tot][0] = tr[tot][1] = 0;//这里注意是tot，不是root！
         tr[root][id] = tot++;
     }
     root  = tr[root][id];
 }
}

 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
int tot;
int ar[MAX];
int tr[MAX][2];

void insert(int x){
    int root = 0;
    for(int i = 17; i >= 0; --i){
        int id = ((x >> i) & 1);
        if(!tr[root][id]){
            tr[tot][0] = tr[tot][1] = 0;
            tr[root][id] = tot++;
        }
        root  = tr[root][id];
    }
}

int getminx(int x){
    int ans = 0;
    int root = 0;
    for(int i = 17; i >= 0; --i){
        int id = ((x >> i) & 1);
        if(tr[root][id]){
            ans = ans << 1;
            root = tr[root][id];
        }
        else {
            ans = ans << 1 | 1;
            root = tr[root][id ^ 1];
        }
    }
    return ans;
}

int getmaxn(int x){
    int ans = 0;
    int root = 0;
    for(int i = 17; i >= 0; --i){
        int id = ((x >> i) & 1);
        if(tr[root][id ^ 1]){
            ans = ans << 1 | 1;
            root = tr[root][id ^ 1];
        }
        else{
            ans = ans << 1;
            root = tr[root][id];
        }
    }
    return ans;
}
void init()
{
    tr[0][0] = tr[0][1] = 0;
    tot = 1;
}
void work(){
    init();
    int l, r;
    cin >> l >> r;
    n = r - l + 1;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i];
        insert(ar[i]);
    }
    for(int i = 1; i <= n; ++i){
        int x = ar[i] ^ l;
        if(getmaxn(x) == r &&
           getminx(x) == l){
            cout << x << endl;
            return;
        }
    }
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}
 

 

博客内容均系原创，未经允许严禁转载！
cf
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Codeforces Round 731 (Div. 3) E. Air Conditioners「思维 + dp」或「思维 + bfs + 堆优化」

							
							

							
Codeforces Round #832 (Div. 2)「D 思维 + 异或前缀和 + 奇偶二分优化」

							
							

							
Editorial of Codeforces Round #735 (Div. 2)

							
							

							
Codeforces Round #719 (Div. 3)

							
							

							
Codeforces Round 729 (Div. 2) C. Strange Function「思维 + 数论」