Div. 2, based on Technocup 2019 Elimination Round 1)】 A B C D E"/>
【Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1)】 A B C D E
A
题意给你一个 0 1 串 有1 就输出HARD 没1就输出EASY
/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll _INF = 0xc0c0c0c0c0c0c0c0;
const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}int main()
{//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n,sum = 0,d;scanf("%d",&n);for(int i = 1;i<=n;++i)scanf("%d",&d),sum+=d;if(sum==0) printf("EASY\n");else printf("HARD\n");//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}B
题意 给你一个n*n正方形 然后长方形顶点分别为 (d,0) (0,d) (n-d,n) (n,n-d) 给你m个点 问你是否在长方形内
我们知道高中学过线性规划 只要把四个方程设出来 在他们之间的也就是在长方形里面的情况了
/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll _INF = 0xc0c0c0c0c0c0c0c0;
const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}int main()
{//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n,d,m,x,y;scanf("%d%d",&n,&d);scanf("%d",&m);while(m--){scanf("%d%d",&x,&y);if((y-x<=d)&&(y-x>=-d)&&(y+x>=d)&&(y+x<=2*n-d)) printf("YES\n");else printf("NO\n");}//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}C
题意 给你一个数字串 问你能不能拆成几个段满足所有段内数字和相同
做法 很容易想到跑一个 9*100的暴力去拆段 但是0的处理需要特殊处理 例如数据
5
9 3 3 3 0
所以你先拆0 0的都不管
然后开始跑暴力 就可以愉快的check了
/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll _INF = 0xc0c0c0c0c0c0c0c0;
const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}
char str[150],str_[150];
int main()
{//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n,sum_ = 0,len = 0;bool flag = false;scanf("%d",&n);scanf("%s",str+1);for(int i = 1;i<=n;++i)sum_+=str[i]-'0';if(sum_==0){printf("YES\n");return 0;}for(int i = 1;i<=n;++i)if(str[i]!='0') str_[++len] = str[i];for(int i = 1;i<=900;++i){if(i>=sum_) break;if(flag) break;int sum = 0;for(int j = 1;j<=len;j++){sum+=str_[j]-'0';if(j==len){if(sum==i&&sum!=sum_){flag = true;break;}break;}if(sum>i) break;if(sum==i) sum = 0;}}if(flag) printf("YES\n");else printf("NO\n");//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}D
给你 n m k 让你在横坐标在 0 - n里面 纵坐标在 0 - m里面找三个点 使得面积等于 n*m/k
我们首先知道 三角形面积只能是整数或者 .5 因为你可以想象成在 0-n 0 -m的长方形里面扣掉三角形构成一个新三角形 扣掉的是整点 面积会产生.5 所以你扣掉的也只能是 .5或者整数 所以我们可以这样做 先让 n*m*2%k是否等于0判断YES 还NO
一开始学长指导想到 先把n质因数分解 m质因数分解 k质因数分解 用k去消除n 和 m中的质因数 然后乘起来就是答案
但是我们用vector实现 其实这步可以用gcd实现 原理一样 就不写了
然后小特判一下就行 因为三角形原先可能是整数或者.5 你需不需要乘2 只要判一下两个乘起来是否就是答案 是就不乘2
//原理是因为你可能没拆完他的2这个质因数 举个例子 我们让n*m*2%k 可能 k剩一个2质因数 这时候%成功了 所以你需要输出原理的 达到输出小数的目的
/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll _INF = 0xc0c0c0c0c0c0c0c0;
const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}
vector<int > vt1,vt2,vt3;
int main()
{//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);long long n,m,k;scanf("%lld%lld%lld",&n,&m,&k);long long tmp_ = (n*m*2)%k;if(tmp_==0){ll n_ = n;tmp_ = n*m*2/k;bool ck = false;printf("YES\n");for(int i = 2;i*i<=n;++i){if(n%i==0){while(n%i==0) vt1.push_back(i),n/=i;}}if(n>1) vt1.push_back(n);for(int i = 2;i*i<=m;++i){if(m%i==0){while(m%i==0) vt2.push_back(i),m/=i;}}if(m>1) vt2.push_back(m);for(int i = 2;i*i<=k;++i){if(k%i==0){while(k%i==0) vt3.push_back(i),k/=i;}}if(k>1) vt3.push_back(k);int sz = vt3.size();for(int i = 0;i<sz;++i){bool flag = false;int tmp = vt3[i];int xb = upper_bound(vt1.begin(),vt1.end(),tmp-1) - vt1.begin();for(int j = xb;j<vt1.size();j++){if(vt1[j]==tmp){vt1[j] = 1;flag = true;break;}}if(!flag){int xb = upper_bound(vt2.begin(),vt2.end(),tmp-1) - vt2.begin();for(int j = xb;j<vt2.size();j++){if(vt2[j]==tmp){vt2[j] = 1;break;}}}}long long tmp1 = 1,tmp2 = 1;for(int i = 0;i<vt1.size();++i)tmp1*=vt1[i];for(int i = 0;i<vt2.size();++i)tmp2*=vt2[i];printf("0 0\n");if(tmp1*tmp2==tmp_){printf("%lld 0\n",tmp1);printf("0 %lld\n",tmp2);}else if(tmp1*2<=n_){printf("%lld 0\n",2*tmp1);printf("0 %lld\n",tmp2);}else{printf("%lld 0\n",tmp1);printf("0 %lld\n",tmp2*2);}}else printf("NO\n");//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}E
题意 给你n个数 定义你可以把他们变成二进制以后调换位置 使得区间异或和为0 那么1个数相同就可以异或为0了
所以你区间和一定要是偶数 如果是奇数一定不能异或 并且虽然是偶数 但是你区间内1个数最大值要小于区间1个数和的一半
举个例子 3 4 5 你就可以拆成 111-3 111001-4 1111110-5 就一定满足了
所以你要判断 每个偶数区间内长度61的内 最大值是否大于区间一半 是就删掉影响
我们定义dp[n][2]
dp[i][0]代表以i结尾的 和为偶数区间
dp[i][1]代表以i结尾的 和为奇数区间
注意统计区间的时候还要加上 (i-1,i)这段的贡献
/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll _INF = 0xc0c0c0c0c0c0c0c0;
const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}
const int MAX_N = 300025;
long long arr[MAX_N];ll work(long long n)
{ll res = 0;while(n){if(n&1) res++;n/=2;}return res;
}
ll dp[MAX_N][3];int main()
{//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);int n;scanf("%d",&n);for(int i = 1;i<=n;++i) scanf("%lld",&arr[i]),arr[i] = work(arr[i]);dp[0][0] = dp[0][1] = 0;dp[1][0] = 0;dp[1][1] = 0;for(int i = 2;i<=n;++i){if(arr[i]&1){dp[i][0] = dp[i-1][1] + (arr[i-1]&1);dp[i][1] = dp[i-1][0] + !(arr[i-1]&1);}else{dp[i][0] = dp[i-1][0] + !(arr[i-1]&1);dp[i][1] = dp[i-1][1] + (arr[i-1]&1);}}ll ans = 0;for(int i = 2;i<=n;++i){ll l_ = max(1,i-61),cnt = 0,sum = arr[i],maxx=arr[i];for(int j = i-1;j>=l_;j--){maxx = max(maxx,arr[j]);sum+=arr[j];if(sum&1) continue;if(maxx>sum/2) cnt++;}ans+=(dp[i][0] - cnt);}printf("%lld\n",ans);//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}
更多推荐
【Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1)】 A
发布评论