点击打开链接cf #153
A
思路:暴力
分析:
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;
}
B
法一
思路:暴力
分析:
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;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<...const int M = 2e5+