分享程序员开发的那些事...
更新时间：2022-08-12 16:17:18
思路：暴力
分析：
1 题目给定n个数 n<=100，要求一个区间内做^能够得到的最大值
2 n最大为100，暴力枚举区间即可。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 110
int n;
int num[MAXN];
int main(){
while(scanf("%d" , &n) != EOF){
for(int i = 0 ; i < n ; i++)
scanf("%d" , &num[i]);
long long max = 0;
for(int i = 0 ; i < n ; i++){
for(int j = i ; j < n ; j++){
long long tmp = num[i];
for(int k = i+1 ; k <= j ; k++)
tmp = tmp^num[k];
if(tmp > max)
max = tmp;
}
}
cout<<max<<endl;
}
return 0;
}
法一
思路：暴力
分析：
1 题目问能否找到两个不同的位置i , j.使得i 和 j交换后序列不是有序的。如果找不到输出-1
2 很明显n<=2时是不可能找到的，输出-1；还有一中特殊的情况就是num[1]=num[2]=...=num[n]，这种也是输出-1.
3 接下来就是暴力枚举i个j的值，然后找到满足的即可。
4 注意如果没有找到应该输出-1，这里不能漏了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
int n;
int num[MAXN];
bool ok(){
for(int i = 2 ; i < n ; i++){
if(!((num[i] >= num[i-1] && num[i] <= num[i+1]) || (num[i] <= num[i-1] && num[i] >= num[i+1]))){
return true;
}
}
return false;
}
int main(){
while(scanf("%d" , &n) != EOF){
bool mark = true;
scanf("%d" , &num[1]);
for(int i = 2 ; i <= n ; i++){
scanf("%d" , &num[i]);
if(num[i] != num[i-1])
mark = false;
}
if(mark || n <= 2)
printf("-1\n");
else{
mark = false;
for(int i = 1 ; i <= n ; i++){
for(int j = i+1 ; j <= n ; j++){
if(num[i] == num[j])
continue;
swap(num[i] , num[j]);
if(ok()){
printf("%d %d\n" , i , j);
mark = true;
break;
}
swap(num[i] , num[j]);
}
if(mark)
break;
}
if(!mark)
printf("-1\n");
}
}
return 0;
}
法二
思路：分类模拟
分析：
1 题目要求找到两个位置交换这两个位置的数，使得序列不是单调的。如果没有输出-1
2 如果n<=2，肯定是不可能找到满足的位置的。
3 那么我们可以通过分析序列总共有几个不同的数字。
如果只有1个就是类似1 1 1...这样的肯定找不到输出-1；
如果是2个那么我们一个for循环找到num[i] != num[i-1]，然后交换它判断是否满足即可。2个的情况可能会有不满足情况，如果都不满足那么就输出-1；
如果是大于等于3个，那么我们只要找出三个不同的数然后交换。但是这三个数原先的排列情况有4种(/，/\，\，\/ 表示增减)。那么我们只要去判断最大值的位置就可以。有三个不同的数那么肯定是可以找到两个位置的。
代码：
#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
#define MAXN 100010
int n;
int num[MAXN];
set<int>s;
bool ok(){
for(int i = 2 ; i < n ; i++){
if(!((num[i] >= num[i-1] && num[i] <= num[i+1]) || (num[i] <= num[i-1] && num[i] >= num[i+1]))){
return true;
}
}
return false;
}
int main(){
while(scanf("%d" , &n) != EOF){
s.clear();
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &num[i]);
s.insert(num[i]);
}
int size = s.size();
/*如果只有1个不同的数*/
if(size == 1 || n <= 2)
printf("-1\n");
/*大于等于3个不同数*/
else if(size >= 3){
int pos[3];
int cnt = 0;
pos[0] = 1;
for(int i = 2 ; i <= n ; i++){
if(num[i] != num[pos[cnt]])
pos[++cnt] = i;
if(cnt == 3)
break;
}
int MAX = max(num[pos[0]] , num[pos[1]]);
MAX = max(MAX , num[pos[2]]);
/*判断最大值位置*/
if(num[pos[0]] == MAX)
printf("%d %d\n" , pos[0] , pos[1]);
else if(num[pos[1]] == MAX)
printf("%d %d\n" , pos[0] , pos[2]);
else if(num[pos[2]] == MAX)
printf("%d %d\n" , pos[1] , pos[2]);
}
/*只有2个不同数*/
else if(size == 2){
bool mark = false;
for(int i = 2 ; i <= n ; i++){
if(num[i] != num[i-1]){
swap(num[i] , num[i-1]);
if(ok()){
printf("%d %d\n" , i , i-1);
mark = !mark;
break;
}
swap(num[i] , num[i-1]);
}
}
if(!mark)/*如果没有找到输出-1*/
printf("-1\n");
}
}
return 0;
}
C
思路：1 枚举起点，维护一个末尾指针。2 另外一种做法是把维护的指针 j 改成二分查找
分析：
1 题目给定一个n个数的有序序列，要求找到最多的方法满足题目要求。
2 我们知道一个有序的序列是很特殊的，假设现在我们的起点是num[i]，那么我们维护一个指针j，使得num[j]-num[i] > d。那么我们知道[i,j)就有j-i-1个数，所以知道了起点那么满足的个数就是C(j-i-1,2){组合公式}。那么我们接下来起点变成了num[i+1]，这个时候正常的做法是j 从 i+2开始，但是由于这个序列是有序的序列有num[i]>num[i-1]，那么肯定 j 之前的数都满足num[j-1]-num[i+1] <= d，所以 j 不用回溯这样就不是O(n^2)而是接近O(n)的复杂度。
3 注意：假设int n = 100000 ， long long ans = n*(n-1)*(n-2)；这个运算实际是得不到ans的，由于n是int,所以运算的时候超出了int范围，所以得到的ans是错误的。应该注意ans是long long 的情况下 n 也要改为 long long.
4 对于一个有序的序列进行二分的时候是可以利用STL的lower_bound() 和 upper_bound()函数的。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int64;
#define MAXN 100010
int64 n , d;/*注意n d要为long long */
int64 num[MAXN];
int main(){
while(cin>>n>>d){
for(int i = 0 ; i < n ; i++)
cin>>num[i];
if(n == 1 || n == 2){
printf("0\n");
continue;
}
int64 maxDis = num[n-1]-num[0];
int64 ans;
if(maxDis <= d){
ans = (n)*(n-1)*(n-2)/6;
cout<<ans<<endl;
}
else{
ans = 0;
int j = 0;/*维护的指针j*/
for(int i = 0 ; i < n-2 ; i++){
if(num[i+2]-num[i] <= d){
for(; j < n ; j++){
if(num[j]-num[i] > d)
break;
}
int64 tmp = j-i-1;
ans += tmp*(tmp-1)/2;
}
}
cout<<ans<<endl;
}
}
return 0;
}
/*二分*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int64;
#define MAXN 100010
int64 n , d;/*注意n d要为long long */
int64 num[MAXN];
int main(){
while(cin>>n>>d){
for(int i = 0 ; i < n ; i++)
cin>>num[i];
if(n == 1 || n == 2){
printf("0\n");
continue;
}
int64 maxDis = num[n-1]-num[0];
int64 ans;
if(maxDis <= d){
ans = (n)*(n-1)*(n-2)/6;
cout<<ans<<endl;
}
else{
ans = 0;
int left , right , mid;
for(int i = 0 ; i < n-2 ; i++){
if(num[i+2]-num[i] <= d){
/*二分查找*/
left = i+3 , right = n;
while(left < right){
mid = left+(right-left)/2;
if(num[mid]-num[i] > d)
right = mid;
else
left = mid+1;
}
int64 tmp = left-i-1;
ans += tmp*(tmp-1)/2;
}
}
cout<<ans<<endl;
}
}
return 0;
}
D
分析：
1 题目的意思给定一个序列p初始为1,2,3....n。再给定一个序列q和一个序列s，做k次的变换
2 每一次的变换有两种可能，第一种是生成一个新的序列p且newp[i] = p[q[i]]，第二种是生成一个新的序列p且newp[q[i]] = p[i]
3 现在题目要问的是把初始化的序列p做k次的变换，能否前k-1次都没有出现序列s，最后一次序列正好为s
4 根据第2点，我们可以推出第一种变换和第二种变换是逆的。也就是说做一次的第一种和一次的第二种变换得到的原来的序列。
5 如果我们执行m1次第一种变换可以使得序列p等于序列s，那么我们先执行(k - m1) / 2次的(第一种变换、第二种变换)组合，再执行m1次第一种变换 即可。
如果我们执行m2次 第二种变换可以使得序列p等于序列s，那么我们先执行(k - m2) / 2次的(第一种变换、第二种变换)组合，再执行m2次第二种变换即可。
所以只要求出其中的m1、m2再判断一下k - m1，k - m2是否是偶数就行了。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 110;
int n , k;
int p[MAXN];
int q[MAXN];
int s[MAXN];
char ans[2][4] = {"NO","YES"};
bool isEqual(){
for(int i = 1 ; i <= n ; i++)
if(s[i] != p[i])
return false;
return true;
}
void init(){
for(int i = 1 ; i <= n ; i++)
p[i] = i;
}
char* solve(){
init();
if(isEqual())
return ans[0];
int m1 = -1;
int m2 = -1;
int tmp[MAXN];
// get m1
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= n ; j++)
tmp[j] = p[q[j]];
memcpy(p , tmp , sizeof(p));
if(isEqual()){
m1 = i;
break;
}
}
init();
// get m2
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= n ; j++)
tmp[q[j]] = p[j];
memcpy(p , tmp , sizeof(p));
if(isEqual()){
m2 = i;
break;
}
}
// judge
if(m1 == -1 && m2 == -1)
return ans[0];
else if(m1 == 1 && m2 == 1 && k > 1)
return ans[0];
else if(m1 != -1 && (k-m1)%2 == 0)
return ans[1];
else if(m2 != -1 && (k-m2)%2 == 0)
return ans[1];
else
return ans[0];
}
int main(){
while(scanf("%d%d" , &n , &k) != EOF){
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &q[i]);
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &s[i]);
cout<<solve()<<endl;
}
return 0;
}
codeforce CROC-MBTU 2012, Final Round (Online version, Div. 2)
Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)(A.思维题，B.思维题)
Codeforces 400 A. Inna and Choose Options 【Codeforces Round #234 (Div. 2)】
Codeforces Round #277(Div. 2) （A Calculating Function, B OR in Matrix, C Palindrome Transformation）