欢迎来到起遇信息学
起遇信息学正处于上线筹建阶段，以下功能已全部开放免费体验： ✅ 完整题库浏览与代码提交评测（C / C++ / Python / Java 等） ✅ 入门到进阶的系列课程试读、作业与考试 ✅ AI 提示、AI 作业分析等智能助教功能 ✅ 赛事模拟与个人能力报告 ✅ 邮箱注册开放 ⏳ 付费课程订阅与微信/支付宝支付通道 ⏳ 手机号登录，微信扫码登录、微信公众号绑定 使用中如遇任何问题，欢迎通过页面底部 **"联系我们"** 与我们沟通。
1.(a|b)可以判断a和b是否有一位均为1.
T1
题目
给定n个01串，每个01串长度为k，求从中取一个非空的01串集合，对于每个位置i(1<=i<=k),这个集合中的每个字符串的第i位上的数加起来应<=集合的大小/2(向上取整)，若这种集合存在，输出YES，否则输出NO.
思路
考虑集合大小。若有一个4个元素的集合满足要求，那么从中任意选出两个串组成的新集合一定可以满足要求。
所以只用枚举不同的串的组合就可以了。对于n=1e5,会超时。
两个串满足条件，那么它们在相同位置上一定只有一个1（也可以没有）。
所以所有相同的串就可以去掉了。由于串的长度最多为4，所以可以将去重后的串变成数字。
最多四位，所以数字的数量最多为2^4=32,这时再进行两两枚举（枚举时要保证数字出现过），复杂度为O(32*32)=O(256),不会超时。
但是枚举的时候对每一位进行判断比较麻烦，可以将(i|j),如果(i|j)>0,那么就一定有一位有两个1.如果(i|j)=0,没有。
代码
#include<bits/stdc++.h>
using namespace std;
long long a[20][1000005];
long long n,k;
bool Flag;
long long b[1000005];
int t[70];
int main(){
freopen("rtmrts.in","r",stdin);
freopen("rtmrts.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cin>>a[j][i];
a[j][i]=a[j][i]%2;
b[i]=b[i]*2+a[j][i];
}
t[b[i]]++;
}
for(int i=0;i<=31;i++){
for(int j=0;j<=31;j++){
if(t[i]&&t[j]){
if(i==0&&t[i]<2)continue;
int ii=i;
int jj=j;
bool flag=1;
if((ii&jj)==0)flag=1;
else flag=0;
if(flag){
Flag=1;
break;
}
}
}
if(Flag)break;
}
if(t[0]!=0)Flag=1;
if(Flag){
cout<<"YES";
} else{
cout<<"NO";
}
return 0;
}
T2
题目
来自克雷姆兰德的学生迪马有一个大小为 的矩阵，其中只包含非负整数。
他希望从矩阵的每一行中选出一个整数，使得所选整数的按位异或严格大于零。
也就是说，他想选择一个整数序列 使得不等式 $a_{1,c_1}\oplus a_{2,c_2}\dots \oplus a_{n,c_n} > 0$成立，其中 是第 行和第 列的矩阵元素。
表示 和 按位异或运算，这里是他的定义。
给你一个n*m的整数矩阵，要求你从每一行里选一个数，使得你选的所有数做异或之后的值>0.问能否做到。能做到，TAK和你选的数的下标。不能，NIE.
思路
异或运算，只要最后进行操作的两个数不一样，结果就一定大于0.
所以可以从先将每行的第一位全部异或起来，得到一个整数tmp再看它是否大于0.大于0则直接输出n个1。
如果不大于0，根据第一句话，可以改变其中的一个数，结果是否会有变化。方便起见，可以从第一行的数开始改。
对于每行数，从左往右遍历一遍,改变tmp(方法见代码),检查tmp是否>0,若大于0，则输出。如果遍历到末尾tmp依然==0，那么就换下一行，重新进行这个操作。换下一行的时候，上一行可以不用变动，因为tmp一直没有改变，那么这一行的所有数字其实都是一样的。
证明：假设没有变动的那一部分全部异或起来的结果为a.正在变动的这一边的数字为b.设最开始的b为b0。如果过程中的a^b不变，那么所有的a^b都等于a^b0==0.因为两个数异或以后的值为0，当且仅当这两个数相等，所以所有的b都等于b0.也就是这一排的数都一样，tmp才不会出现变动。所以枚举下一排的时候，也不必改变上一排的指针，让其待在最后一个位置就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[505][505];
int ans[505];
int main(){
freopen("badxor.in","r",stdin);
freopen("badxor.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
int tmp=0;
for(int i=1;i<=n;i++){
ans[i]=1;
tmp^=a[i][1];
}
int p=1;
while(tmp==0&&p<=n+1){
bool flag=0;
for(int i=2;i<=m;i++){
tmp^=a[p][i-1];
tmp^=a[p][i];
if(tmp>0){
flag=1;
ans[p]=i;
break;
}
}
p++;
if(flag){
break;
}
}
if(tmp){
cout<<"TAK\n";
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
} else{
cout<<"NIE";
}
return 0;
}
T3
题目
给你两个数组a,b。a的大小为n,b的大小为m.对于每个 （），你需要选择一个 （），并令 ，其中 表示按位与运算.注意，对于不同的 ，你可以选择相同的 。
请你求出最小的 ，其中 表示按位或运算。（n,m<=200,0<=$a_i,b_i<=$2^9）
思路
由于数字最大为2^9即512,且可以看出答案不会超过512(最大位数就9位，只有&和|运算，位数不会超)所以可以枚举答案p,从0到512
对于每个答案，i:1~n模拟选a的过程，j:1~m模拟选b的过程。对于每个数，我们要判断与（&）上它之后会不会超出p.如果会超出p,那么这个数就不行。若这一行所有的数都不行，那么这个数就无法完成。如果a中的每个数都行，那么p就是最小的可行解。怎么判断是否会超过见下：
如果成立，则这个不可行(因为有多出来的1，做|的时候也会多出来这个1，按位与下来得到的答案就会大于p).从小到大枚举p,保证第一个合法的就会直接被输出，不会被漏掉。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[205];
int b[205];
int main(){
freopen("bit.in","r",stdin);
freopen("bit.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
for(int p=0;p<512;p+=1){
bool Flag=1;
for(int i=1;i<=n;i++){
bool flag=1;
for(int j=1;j<=m;j++){
if(((a[i]&b[j])|p)==p){
flag=0;
break;
}
}
if(flag)Flag=0;
}
if(Flag){
cout<<p;
return 0;
}
}
return 0;
}
T4
题目
定义强大数为2的幂或阶乘。
给定一个整数n(n<=1e12),求出最小的k,使得n能表示为k个互不相同的强大数之和。
分析
每个整数一定能表示为强大数。因为它的二进制表示就是一种强大数方案。
我们可以先求出范围内的所有阶乘数，大概是14个阶乘数，再2^14枚举选择阶乘数的集合，然后求出剩下的数字的二进制表示中有多少1即可。注意阶乘数的集合中不要放1和2，因为它们也是2的次幂。
代码
/*
1.求阶乘的数组
2.对于每个数，先用阶乘凑，再用二进制
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;
vector<LL>v;
LL n;
bool vis[30];
int ans=-1;
void dfs(int x){
if(x>=v.size()){
LL tmp=0;
int cnt=0;
for(int i=0;i<v.size();i++){
if(vis[i]){
tmp+=v[i];
cnt++;
}
}
LL res=n-tmp;
if(res>=0){
while(res>0){
if(res&1)cnt++;
res>>=1;
// cout<<res<<"\n";
}
ans=min(ans,cnt);
}
return;
}
vis[x]=1;
dfs(x+1);
vis[x]=0;
dfs(x+1);
}
void sol(){
cin>>n;
ans=1e9;
dfs(0);
cout<<ans<<"\n";
return;
}
int main(){
freopen("factorials.in","r",stdin);
freopen("factorials.out","w",stdout);
LL tmp=2;
for(int i=3;;i++){
tmp*=i;
if(tmp>(LL)1e12)break;
v.push_back(tmp);
}
cin>>t;
while(t--){
sol();
}
return 0;
}
T5
贪心。算性价比，枚举，i,j.用第i个尽可能的填满，用第j个来填剩下的，求花费，再求最小。
代码
#include<bits/stdc++.h>
using namespace std;
int n,l;
struct node{
long long cost,sz;
}a[50];
int c[35];
int po[35];
bool cmp(node x,node y){
long long res1=(long long)(x.cost)*y.sz;
long long res2=(long long)(x.sz)*y.cost;
return res1<res2;
}
int main(){
freopen("party.in","r",stdin);
freopen("party.out","w",stdout);
po[0]=1;
for(int i=1;i<=30;i++)po[i]=po[i-1]*2;
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>c[i];
a[i].cost=c[i];
a[i].sz=po[i-1];
}
long long ans=1e18;
for(int i=1;i<=n;i++){
long long tmp=0;
long long co=a[i].cost;
long long s=a[i].sz;
long long l_=l;
tmp+=(l_/s)*co;
l_=l_-(l_/s*s);
long long minn=1e9;
for(int j=1;j<=n;j++){
long long sz1=a[j].sz;
int ne=0;
if(l_%sz1!=0){
ne=1;
}
ne+=l_/sz1;
long long dsfa=(ne*a[j].cost);
minn=min(minn,dsfa);
}
tmp+=minn;
if(tmp<ans){
ans=tmp;
}
}
cout<<ans;
return 0;
}
T6
代码
#include<bits/stdc++.h>
using namespace std;
int T;
string s,t;
long long n,k;
void sol(){
cin>>n>>k;
cin>>s>>t;
long long onea=0,oneb=0,onec=0;
for(int i=0;i<n;i++){
if(s[i]=='1')onea++;
if(t[i]=='1')oneb++;
if(s[i]!=t[i])
onec++;
}
unsigned long long now1=1,nowc=0;
for(int i=1;i<=k;i++){
unsigned long long tmp1=now1+nowc;
unsigned long long tmp2=now1*2-1;
now1=tmp1;
nowc=tmp2;
}
unsigned long long ans=0;
ans+=onec*(n-onec)*nowc;
ans+=onea*(n-onea)*now1;
ans+=oneb*(n-oneb)*now1;
cout<<ans<<"\n";
}
int main(){
freopen("binary.in","r",stdin);
freopen("binary.out","w",stdout);
cin>>T;
while(T--){
sol();
}
return 0;
}
0 条评论
目前还没有评论...
Be the first to comment!