当前位置：网站首页>2022/8/9
2022/8/9
2022-08-10 03:40:00 【killer_queen4804】
活动地址：CSDN21天学习挑战赛
1141C - Polycarp Restores Permutation
假设p[1]为0，那么就可以通过q数组来求出每个p[i]相对于p[1]的增量了，然后找出最小的值这个值就是1，让这个数变为1的代价是x，每个数都加上x原排列就出来了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=9999973;
const int N = 2e5+5;
ll n,a[200005],vis[400005];
int main(){
scanf("%lld",&n);
a[1]=0;
ll minn=0;
for(int i=2;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1],minn=min(minn,a[i]);
for(int i=1;i<=n;i++) a[i]=a[i]+(1LL-minn);
ll m=0;
for(int i=1;i<=n;i++){
if(a[i]>n||a[i]<=0){m=-10;break;}
if(!vis[a[i]]) vis[a[i]]=1,m++;
}
if(m==n){
for(int i=1;i<=n;i++) printf("%lld ",a[i]);
}
else printf("-1");
system("pause");
return 0;
}
1395C - Boboniu and Bit Operations 状压dp 或 思维
先说状压dp的做法，f[i][j]表示已经求出了c[i],前i个c[i]是否可以或成j，我们枚举a，枚举b,枚举当前状态也就是前i个c[i]或的和，然后枚举a[i]&b[j]的子集也就是c[i]的子集，看看是否可以转移到f[i][j],由于是枚举子集，所以时间复杂度会减少很多
C. Boboniu and Bit Operations(状压)_issue是fw的博客-CSDN博客
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=9999973;
const int N = 2e5+5;
ll n,m,a[205],b[205],f[205][1<<10];
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int j=1;j<=m;j++) scanf("%lld",&b[j]);
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ll v=a[i]&b[j];
for(int u=0;u<(1<<9);u++){
if((u&v)!=v) continue;//v中的1 u应该都有
for(int w=v;w;w=(w-1)&v)
f[i][u]|=f[i-1][u^w];
f[i][u]|=f[i-1][u];
}
}
for(int i=0;;i++)
if(f[n][i]){printf("%d ",i);break;}
system("pause");
return 0;
}
思维的做法：因为或运算只会让数不变或增加，所以最优的状态应该是不变，所以我们应该让c[i]都相同且尽量最小，如果c[i]不相同的话或出来的值会大于所有的c[i]这显然是不行的，所以最小值应该会出现在所有c[i]都相同的情况下，那我们就枚举测试每个答案行不行就可以了，因为数据范围小也用不到二分
C. Boboniu and Bit Operations（位运算操作+思维）Codeforces Round #664 (Div. 2)_unique_pursuit的博客-CSDN博客
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=9999973;
const int N = 2e5+5;
ll n,m,a[205],b[205];
bool check(ll s){
for(int i=1;i<=n;i++){
ll flag=0;
for(int j=1;j<=m;j++){
ll tmp=a[i]&b[j];
if((tmp|s)==s) flag=1;
if(flag) break;
}
if(!flag) return false;
}
return true;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
for(int i=0;i<(1<<10);i++){
if(check(i)){printf("%d",i);break;}
}
system("pause");
return 0;
}
J-Melborp Elcissalc_"蔚来杯" dp 前缀和小技巧
这个题也是用到了之前用到的前缀和技巧，但是比之前那个好像更难了点，对于一个前缀和来说，要求有多少区间的和是k的倍数，那我们可以对前缀和数组的每个数都取余k，之后每个数出现了x次就有C(x,2)个区间是k的倍数，0例外是C(x+1,2),因为1个0也满足条件；对于一个数组我们需要知道这个数组用到了0-k-1中的哪些数，这些数出现了多少次以及一共有多少区间符合条件，那我们就设一个dp[i][len][s]表示前i个数中用了len个，可以产生s个符合条件的区间，枚举到i，枚举想要用num个i，那么转移方程就是dp[i][len+num][s+C(num,2)]=dp[i-1][len][s],要是放0的话因为例外所以要是dp[i][len+num][s+C(num+1,2)],代码应该是因为方便转移将i都加了1位
2022牛客暑期多校训练营7 个人题解 更新至5题 - 知乎 (zhihu.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll fac[105];
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll getinv(ll a,ll mod){return qpow(a,mod-2);}
ll C(ll x,ll y){//求组合数模板
return fac[x]*getinv(fac[y],mod)%mod*getinv(fac[x-y],mod)%mod;
}
ll n,k,t,dp[70][70][3005],c[105][105];
int main(){
fac[0]=1;
for(ll i=1;i<=70;i++) fac[i]=fac[i-1]*i%mod;
for(ll i=0;i<=64;i++)
for(ll j=i;j<=65;j++)
c[j][i]=C(j,i);
scanf("%lld%lld%lld",&n,&k,&t);
dp[0][0][0]=1;
for(int i=1;i<=k;i++)
for(int len=0;len<=n;len++)
for(int s=0;s<=t;s++)
if(dp[i-1][len][s])
for(int num=0;num+len<=n;num++){
if(i==1) dp[i][num+len][c[num+1][2]+s]=(dp[i][num+len][c[num+1][2]+s]+dp[i-1][len][s]*c[num+len][num]%mod)%mod;
else dp[i][num+len][c[num][2]+s]=(dp[i][num+len][c[num][2]+s]+dp[i-1][len][s]*c[num+len][num]%mod)%mod;
}
printf("%lld",dp[k][n][t]);
system("pause");
return 0;
}
P1896 [SCOI2005] 互不侵犯 - 洛谷 | 状态压缩dp
之前做过的一道题，当时的思想没有跟上现在来重新做一遍，这其实很像n皇后问题，之前是用搜索做，现在是用代码更简单的dp来做，用一个二进制数来表示一行的放置情况，预处理出所有合法情况之后枚举每行的情况，和上一行作比较如果可行就枚举已经放了多少个国王来进行转移
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=998244353;
const int N = 2e5+5;
ll n,m,dp[10][1<<9][105];
ll ok[1<<9],cnt=0;
int main(){
scanf("%lld%lld",&n,&m);
for(int i=0;i<1<<n;i++){
if(i&i>>1||i&i<<1) continue;
ok[++cnt]=i;
}
dp[0][1][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int k=1;k<=cnt;k++){
if(ok[j]&ok[k]||ok[j]>>1&ok[k]||ok[j]<<1&ok[k]) continue;
ll x=__builtin_popcount(ok[j]),y=__builtin_popcount(ok[k]);
for(int l=y;l<=m-x;l++) dp[i][j][l+x]+=dp[i-1][k][l];
//第k种情况已经有y个了，前i-2行可能也有放置的国王，所以从y开始枚举
}
ll ans=0;
for(int i=1;i<=cnt;i++) ans+=dp[n][i][m];
printf("%lld\n", ans);
system("pause");
return 0;
}
P1879 [USACO06NOV]Corn Fields G - 洛谷 | 状压dp
这题和上一题是差不多的思路，这一个还少了个条件不需要考虑放的个数了，但是需要判断是不是和初始的情况一致，这个一个for循环就可以判断了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=100000000;
const int N = 2e5+5;
ll n,m,dp[20][1<<12],a[20][20];
ll ok[1<<12],cnt=0;
int main(){
scanf("%lld%lld",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&a[i][j]);
for(int i=0;i<1<<n;i++){
if(i&i>>1||i&i<<1) continue;
ok[++cnt]=i;
}
dp[0][1]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=cnt;j++)
for(int k=1;k<=cnt;k++){
if(ok[j]&ok[k]) continue;
ll flag=1;
for(int l=1;l<=n;l++)
if(ok[j]>>l-1&1!=a[i][n-l+1]){flag=0;break;}
if(flag) dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
}
ll ans=0;
for(int i=1;i<=cnt;i++) ans=(ans+dp[m][i])%mod;
printf("%lld\n", ans);
system("pause");
return 0;
}
P2148 [SDOI2009] E&D - 洛谷 | sg函数
看了一下sg函数，套路就是根据题意打表然后找规律，求出sg函数之后判断异或和
这是打的表
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=100000000;
const int N = 2e5+5;
ll t,n;
// ll sg(ll a,ll b){
// if(a%2&&b%2) return 0;
// if(a%2&&b%2==0) return sg(b,a);
// if(a%2==0&&b%2) return sg(a,b+1);
// if(a%2==0&&b%2==0) return sg(a/2,b/2)+1;
// }
// ll db(ll a,ll b){
// if(dbsg[a][b]) return dbsg[a][b];
// vector<ll>v;
// for(ll i=1;i<=a;i++) v.push_back(db(i,a-i));
// for(ll i=1;i<=b;i++) v.push_back(db(i,b-i));
// sort(v.begin(),v.end());
// ll x=0;
// for(int i=0;i<v.size();i++){
// if(x!=v[i]) return dbsg[a][b]=x;
// x=v[i]+1;
// }
// return x;
// }
std::map<pair<ll,ll>, ll> sg;
int calc(pair<ll,ll> c) {
if (sg.count(c)) return sg[c];
std::vector<int> s;
for(int i=1;i<=c.first-1;i++) s.push_back(calc({i, c.first - i}));
for(int i=1;i<=c.second-1;i++) s.push_back(calc({i, c.second - i}));
std::sort(s.begin(), s.end());
s.erase(std::unique(s.begin(), s.end()), s.end());
ll lst = -1;
for (auto i : s) {
if (i != lst + 1) return sg[c] = lst + 1;
lst = i;
}
return sg[c] = lst + 1;
}
int main(){
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++)
cout<<calc({i,j})<<"\t";
cout<<"\n";
}
system("pause");
return 0;
}
这是ac代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=100000000;
const int N = 2e5+5;
ll t,n;
ll sg(ll a,ll b){
if(a%2&&b%2) return 0;
if(a%2&&b%2==0) return sg(b,a);
if(a%2==0&&b%2) return sg(a,b+1);
if(a%2==0&&b%2==0) return sg(a/2,b/2)+1;
}
int main(){
scanf("%lld",&t);
while(t--){
ll res=0;
scanf("%lld",&n);
for(int i=2;i<=n;i+=2){
ll a,b;
scanf("%lld%lld",&a,&b);
res^=sg(a,b);
}
if(res) printf("YES\n");
else printf("NO\n");
}
system("pause");
return 0;
}边栏推荐
- Take you to an in-depth understanding of the version update of 3.4.2, what does it bring to users?
- 自定义训练，使用Generator dataset迭代数据报错
- 郑州轻工业大学OJ合集（C语言）【正在整理】
- 【MindSpore功能】运行SSD-MobileNetV1 FPN样例报错
- 电话自动拨号在电脑上自动拨打
- 如何将 @Transactional 事务注解运用到炉火纯青？
- It's almost 35, still "did a little"?What happened to the test workers who had been in the industry for a few years?
- 测试工作管理与规范
- order by注入与limit注入
- 处理一些数据
猜你喜欢
随机推荐
Qt编写物联网管理平台50-超强跨平台
数据库学习真难，头大，有偿提问
【网络迁移】Pytorch中的F.interpolate对应MindSpore哪个方法
2022华数杯思路分析
Embedded Sharing Collection 32
GBase 8s打开工具就报错“配置文件有误” ！！！为什么
【单调栈】【概念讲解＆＆模板代码】
【MindSpore】在训练过程中的step代表什么？
学习总结week4_2正则
数据库设计中反映用户对数据要求的模式叫什么
Evaluation and Construction of Enterprise Network Security Capability from the Sliding Ruler Model
MySQL数据库初体验
ZZULIOJ:1024: 计算字母序号
互联网家装驶入深水区：谁在求变，又有谁在裸泳？
js原型和原型链以及原型继承
文件操作【c语言】
Flink学习15：Flink自定义数据源
ZZULIOJ:1022: 三整数排序
模型部署ONNX学习
sql优化