省赛拖了大哥们的后腿,感觉随便补个正常一队水平的人,我们一队肯定能AK。只能说自己真的菜,全程帮不上什么忙,还负贡献,真的想笑
B
暴力sg
#include
#define ll long long
#define ull unsigned long long
constexpr int N=1e6;
int sg[N+5];
int vis[N+5];
void getsg(){
for (int i=1;iN;i++){
// vis[sg[i-1]]=i;
int res=sqrt(1.0*i);
if (i==res*res){
for (int k=1;kres;k++){
vis[sg[i-(i-res*res+k*res)]]=i;
}
}else{
for (int k=0;kres;k++){
vis[sg[i-(i-res*res+k*res)]]=i;
}
}
while (vis[sg[i]]==i){
sg[i]++;
}
}
}
void yrzr(){
getsg();
int n;
std::cin>>n;
int sum=0;
for (int i=1;in;i++){
int x;
std::cin>>x;
sum^=sg[x];
}
if (sum){
std::cout"Firstn";
}else{
std::cout"Secondn";
}
}
D
大哥赛后说是HN省选dp原题(见状压dp P3188 [HNOI2007] 梦幻岛宝珠),然后这个题比那个题范围还要大,看完题解发现是贪心题,但是还是按位分组的思想去解决问题
首先对于一个目标物品来说,它的需求可以表示为几个二进制位的组合,然后我们分解每一个目标物品到位上,然后将其按位合并,最后可以表示为一个二进制串(用数组表示)
然后对于每一件物品,重量小的物品可以合并成大物品,但大物品不能拆解成小物品,所以我们按位从小到大枚举目标物品数组,贪心地用小物品去满足当前位的数量,然后将剩下的物品贪心地两两合并成下一位的物品。
简要的说就是:目标物品总体可以表示为一个数组,然后拥有的物品贪心从小到大去填补目标重量
#include
#define ll long long
#define ull unsigned long long
constexpr int inf=1e9;
std::priority_queueint,std::vectorint>,std::greaterint>> q[5105];
void yrzr(){
int n;
std::cin>>n;
for (int i=1;in;i++){
int x,y;
std::cin>>x>>y;
q[x].push(y);
}
int m;
std::cin>>m;
std::vectorint> sum(5105);
while (m--){
int t,h;
std::cin>>t>>h;
while (h){
if (h&1) sum[t]++;
h>>=1;
t++;
}
}
for (int i=0;i5100;i++){
if (sum[i]>=2){
int temp=sum[i],p=i;
sum[i]=0;
while (temp){
if (temp&1) sum[p]++;
temp>>=1;
p++;
}
}
}
int ans=0;
for (int i=0;i5100;i++){
if (q[i].size()sum[i]){
std::cout"-1n";
return;
}
for (int j=1;jsum[i];j++){
ans+=q[i].top();
q[i].pop();
}
while (q[i].size()>=2){
int temp=q[i].top();
q[i].pop();
temp+=q[i].top();
q[i].pop();
q[i+1].push(temp);
}
}
std::coutans;
}
F
图论题,首先Floyed求出一个字母变成另一个字母的最小花费,然后对于两个不同的字母,暴力预处理出他们变成同样字母的最小花费。最后A串不动,枚举B串位置,求最小即可
可能有重边,输入时
d
i
s
dis
dis取最小
#include
#define int long long
#define ull unsigned long long
constexpr int inf=1e16;
void yrzr(){
服务器托管网 int n,m;
std::cin>>n>>m;
std::vectorint> a(n),b(n);
for (int i=0;in;i++){
std::cin>>a[i];
}
for (int i=0;in;服务器托管网i++){
std::cin>>b[i];
}
std::vectorstd::vectorint>> dis(405,std::vectorint>(405,inf)),c(405,std::vectorint>(405,inf));
for (int i=1;im;i++){
int x,y,z;
std::cin>>x>>y>>z;
dis[x][y]=std::min(dis[x][y],z);
}
for (int i=1;i400;i++){
dis[i][i]=c[i][i]=0;
}
for (int k=1;k400;k++){
for (int i=1;i400;i++){
for (int j=1;j400;j++){
dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
for (int i=1;i400;i++){
for (int j=1;j400;j++){
for (int k=1;k400;k++){
c[i][j]=std::min(c[i][j],dis[i][k]+dis[j][k]);
}
}
}
int ans=inf;
for (int i=0;in;i++){
int sum=0;
bool ok=1;
for (int j=0;jn;j++){
if (c[a[j]][b[(j+i)%n]]==inf){
ok=0;
break;
}else{
sum+=c[a[j]][b[(j+i)%n]];
}
}
if (ok){
ans=std::min(ans,sum);
}
}
if (ans==inf){
std::cout"-1n";
}else{
std::coutans"n";
}
}
I
数位dp,不知道省赛脑子犯了什么抽,受前几天一道数位dp,直接把状态数组压入map暴力记忆化的影响,想当然的觉得这题也是这么做,大哥直接提出时间复杂度是不够的。后面大哥们说是数位dp加个容斥。
补题的时候也一直在想数位dp+容斥,发现自己容斥不出来(容斥见识的得太少了),看了题解后发现只要一个数位dp就可以了
突然发现这题的思想其实跟前几天做的数位dp是一样的,甚至状态更简单,我们最重要的状态其实就只有当前位第几位,然后还要知道现在有多少个不同的数,这就足够了。因为对于这10个数字来说,后面的数字它只有两种身份,之前选了/没选,所以当前位相同,之前不同的数字个数相同,剩下的方案数就相同,就可以用记忆化。(赛时真的蠢傻了,这种套路思想学数位dp的时候见过很多了)
#include
#define ll long long
#define ull unsigned long long
constexpr ll mod=1e9+7;
ll f[200005][12][2][2];
int now[12];
void yrzr(){
int n;
std::cin>>n;
std::vectorint> a(n+1),b(n+1);
for (int i=1;in;i++){
char ch;
std::cin>>ch;
a[i]=ch-'0';
}
for (int i=1;in;i++){
char ch;
std::cin>>ch;
b[i]=ch-'0';
}
reverse(a.begin()+1,a.end());
reverse(b.begin()+1,b.end());
int A;
std::cin>>A;
std::functionll(int,int,int,int)> dfs=[&](int len,int sum,int dif1,int dif2){
if (len==0){
return 1LL*(sum==A);
}
if (sum>A){
return 0LL;
}
if (dif1&&dif2&&f[len][sum][dif1][dif2]){
return f[len][sum][dif1][dif2];
}
int x=(dif1?0:a[len]),y=(dif2?9:b[len]);
ll res=0;
for (int i=x;iy;i++){
if (now[i]){
now[i]++;
res=(res+dfs(len-1,sum,dif1|(a[len]!=i),dif2|(b[len]!=i)))%mod;
now[i]--;
}else{
now[i]++;
res=(res+dfs(len-1,sum+1,dif1|(a[len]!=i),dif2|(b[len]!=i)))%mod;
now[i]--;
}
}
if (dif1&&dif2) f[len][sum][dif1][dif2]=res;
return res;
};
std::coutdfs(n,0,0,0);
}
J
分别枚举圆心在三个坐标轴,然后二分圆的半径,接下来考虑怎么check,对于一个点来说,我们去计算出它在球内时,圆心所在的区间,存下区间左右端点和权值(表示是左端点还是右端点),遍历一遍看是否有点满足题意即可
#include
#define ll long long
#define ull unsigned long long
constexpr int N=1e5+5;
int n;
ll x[N],y[N],z[N];
struct node{
double pos;
int val;
}a[N1];
bool check(double r){
int cnt=0;
for (int i=1;in;i++){
double res=r*r-y[i]*y[i]-z[i]*z[i];
if (res0) continue;
res=sqrt(res);
a[++cnt]={x[i]-res,1};
a[++cnt]={x[i]+res,-1};
}
std::sort(a+1,a+1+cnt,[&](node i,node j){
return i.posj.pos;
});
int sum=0;
for (int i=1;icnt;i++){
sum+=a[i].val;
if (sum>=n/2){
return 1;
}
}
cnt=0;
for (int i=1;in;i++){
double res=r*r-x[i]*x[i]-z[i]*z[i];
if (res0) continue;
res=sqrt(res);
a[++cnt]={y[i]-res,1};
a[++cnt]={y[i]+res,-1};
}
std::sort(a+1,a+1+cnt,[&](node i,node j){
return i.posj.pos;
});
sum=0;
for (int i=1;icnt;i++){
sum+=a[i].val;
if (sum>=n/2){
return 1;
}
}
cnt=0;
for (int i=1;in;i++){
double res=r*r-x[i]*x[i]-y[i]*y[i];
if (res0) continue;
res=sqrt(res);
a[++cnt]={z[i]-res,1};
a[++cnt]={z[i]+res,-1};
}
std::sort(a+1,a+1+cnt,[&](node i,node j){
return i.posj.pos;
});
sum=0;
for (int i=1;icnt;i++){
sum+=a[i].val;
if (sum>=n/2){
return 1;
}
}
return 0;
}
void yrzr(){
std::cin>>n;
for (int i=1;in;i++){
std::cin>>x[i]>>y[i]>>z[i];
}
double l=0,r=1e6;
for (int i=0;i50;i++){
double mid=(l+r)/2;
if (check(mid)){
r=mid;
}else{
l=mid;
}
}
std::coutstd::fixedstd::setprecision(7)l;
}
K
补的时候相成状压了,然后状压+矩阵加速???,发现不会写
然后看了题解知道是容斥了,所以以后对于这种小数据除了状压也有可能是容斥
想到容斥就很好做了,每次直接暴力二进制枚举哪些城市不去,在转移的矩阵和答案矩阵上去掉那些转移点,然后dp矩阵加速即可
#include
#define ll long long
#define ull unsigned long long
constexpr ll mod=1e9+9;
constexpr int N=25;
struct Matrix{
int lenn,lenm;
ll a[N][N];
Matrix() {memset(a,0,sizeof(a));}
Matrix operator*(const Matrix &b)const{
if (lenm==b.lenn){
Matrix res;
res.lenn=lenn;
res.lenm=b.lenm;
for (int i=1;ilenn;i++){
for (int j=1;jb.lenm;j++){
for (int l=1;llenm;l++){
res.a[i][j]=(res.a[i][j]+a[i][l]*b.a[l][j]%mod)%mod;
}
}
}
return res;
}
}
Matrix operator+(const Matrix &b)const{
if (lenn==b.lenn&&lenm==b.lenm){
Matrix res;
res.lenn=lenn;
res.lenm=lenm;
for (int i=1;ilenn;i++){
for (int j=1;jlenm;j++){
res.a[i][j]=a[i][j]+b.a[i][j];
}
}
return res;
}
}
Matrix operator-(const Matrix &b)const{
if (lenn==b.lenn&&lenm==b.lenm){
Matrix res;
res.lenn=lenn;
res.lenm=lenm;
for (int i=1;ilenn;i++){
for (int j=1;jlenm;j++){
res.a[i][j]=a[i][j]-b.a[i][j];
}
}
return res;
}
}
};
int s[10],n,m,k,d;
int a[25][25];
ll solve(int mask){
Matrix e,f,ans;
ans.lenn=1;
ans.lenm=f.lenn=f.lenm=e.lenn=e.lenm=n;
std::vectorint> vis(n+1);
for (int i=1;in;i++){
for (int j=1;jn;j++){
e.a[i][j]=a[i][j];
}
f.a[i][i]=1;
ans.a[1][i]=1;
}
for (int i=1;ik;i++){
if (mask&(1(i-1))){
int x=s[i];
for (int j=1;jn;j++){
e.a[x][j]=e.a[j][x]=0;
}
vis[x]=1;
ans.a[1][x]=0;
}
}
int temp=d;
while (temp){
if (temp&1) f=f*e;
e=e*e;
temp>>=1;
}
ans=ans*f;
ll sum=0;
for (int i=1;in;i++){
if (vis[i]) continue;
sum=(sum+ans.a[1][i])%mod;
}
return sum;
}
void yrzr(){
std::cin>>n>>m>>k>>d;
d--;
for (int i=1;ik;i++){
std::cin>>s[i];
}
for (int i=1;im;i++){
int x,y;
std::cin>>x>>y;
a[x][y]=a[y][x]=1;
}
ll ans=0;
for (int i=0;i(1k);i++){
if (__builtin_popcount(i)&1){
ans=(ans-solve(i)+mod)%mod;
}else{
ans=(ans+solve(i))%mod;
}
}
std::coutans;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
shell命令概述 Shell作用:命令解释器 介于操作系统内核与用户之间,负责解释命令行 获得命令帮助 内部命令help 命令的“–help” 选项 使用man命令阅读手册页 命令行编辑的几个辅助操作 Tab键:自动补齐 反斜杠“”:强制换行 快捷键 Ct…