头像

xhQYm




离线:1天前


新鲜事 原文

xhQYm
1天前
恭喜这个菜逼模拟赛三次T1分炸掉50+



xhQYm
1天前

跟yls的短小精悍的代码差别甚大。。。

但是奆佬们还是帮忙看看吧

f[i][j]表示当前状态为j且前i号搞定了的情况数量
check1(x)表示状态x可不可行(单行,就是有没有奇数个连在一块的1)
check2(x,y)表示当前行为x上一行为y,这种状态下x,y冲不冲突

感觉思路有问题

(一会就去听一遍课)

#include<bits/stdc++.h>
using namespace std;
const int N=12;
int n,m,f[N][1<<11];
bool check1(int st){
    int cnt=2;
    for(int i=0;i<m;i++){
        if(st>>i&1) cnt++;
        else{
            if(cnt&1)  return false;
            cnt=2;
        }
    }
    if(cnt&1) return false;
    return true;
}
bool check2(int st1,int st2){
    for(int i=0;i<m;i++)
        if(!(st1>>i&1)&&(st2>>i&1)) return false;
    return true;
}
int main(){
    while(1){
        scanf("%d%d",&n,&m);
        if(!n&&!m) return 0;
        for(int i=0;i<1<<m;i++) f[1][i]=1;
        for(int i=2;i<=n;i++)
            for(int j=0;j<1<<m;j++){
                if(!check1(j)) continue;
                for(int k=0;k<1<<m;k++){
                    if(!check1(k)||!check2(j,k)) continue;
                    f[i][j]+=f[i-1][k];
                }
            }
        int ans=0;
        for(int i=0;i<1<<m;i++)
            ans+=f[n][i];
        printf("%d\n",ans);
    }
    return 0;
}



xhQYm
2个月前

洛谷上的【P1962 斐波那契数列】

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2;
int n,p=1e9+7;
void mul1(int c[],int a[],int b[][N]){
    int temp[N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            temp[i]=(temp[i]+(ll)a[j]*b[j][i])%p;
    memcpy(c,temp,sizeof temp);
}
void mul2(int c[][N],int a[][N],int b[][N]){
    int temp[N][N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                temp[i][j]=(temp[i][j]+(ll)a[i][k]*b[k][j])%p;
    memcpy(c,temp,sizeof temp);
}
int f[N],a[N][N];
int main(){
    scanf("%d",&n);
    if(n<=2){
        printf("1");
        return 0;
    }
    f[0]=1,f[1]=1;
    a[0][0]=0,a[1][0]=1,a[0][1]=1,a[1][1]=1;
    n-=2;
    while(n){
        if(n&1) mul1(f,f,a);
        mul2(a,a,a),n>>=1;
    }
    printf("%d",f[1]%p);
    return 0;
}




xhQYm
7个月前

upd 2020/8/2: 修复错字


这是一道矩阵乘法的最基础的题面。做对这题只需要按题意模拟即可。

记得开 long long

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int n,m,k,a[N][N],b[N][N],c[N][N];
void mul()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            for(int p=1;p<=m;p++)
                c[i][j]+=(a[i][p]*b[p][j]);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);
    scanf("%lld",&k);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=k;j++)
            scanf("%lld",&b[i][j]);
    mul();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
            printf("%lld ",c[i][j]);
        putchar('\n');
    }
    return 0;
}

闲话:矩阵乘法可以用来优化dp,加速运算。

推荐题面:XR-1 分块斐波那契前n项和




xhQYm
7个月前

此题解为提供封装版字符串哈希模板,,,可自取

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=100010,P=131;
int M;
struct Hash
{
    int n;
    char str[N];
    ull h[N],p[N];
    void init()
    {
        p[0]=1;
        for(int i=1;i<=n;i++) h[i]=h[i-1]*P+str[i],p[i]=p[i-1]*P;
    }
    ull get(int l,int r){return h[r]-h[l-1]*p[r-l+1];}
};
Hash h;
int main()
{
    scanf("%d%d",&h.n,&M);
    scanf("%s",h.str+1);
    h.init();
    while(M--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(h.get(l1,r1)==h.get(l2,r2)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

复习的时候顺便改成了封装版




xhQYm
7个月前

多个棋子是怎么个操作法?是如果所有棋子都不可以移动就算输?




xhQYm
7个月前

树状数组裸题

直接进行树状数组即可,线段树当然也行(但是树状数组简单呀)

模板:

struct BIT {
    int tr[N];
    int lowbit(int x) { return x & (-x); }
    void modify(int x, int c) {
        for (; x <= n; x += lowbit(x)) {
            tr[x] += c;
        }
    }
    int check(int x) {
        int ans = 0;
        for (; x; x -= lowbit(x)) {
            ans += tr[x];
        };
        return ans;
    }
} TR;

之后就是这题代码了,,,

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, tmp, p;
char opt[2];
struct BIT {
    int tr[N];
    int lowbit(int x) { return x & (-x); }
    void modify(int x, int c) {
        for (; x <= n; x += lowbit(x)) {
            tr[x] += c;
        }
    }
    int check(int x) {
        int ans = 0;
        for (; x; x -= lowbit(x)) {
            ans += tr[x];
        };
        return ans;
    }
} TR;
int main() {
    scanf("%d%d", &n, &m);
    for (; m; m--) {
        scanf("%s", opt);
        if (*opt == 'A') {
            scanf("%d", &tmp);
            printf("%d\n", TR.check(tmp));
        } else if (*opt == 'B') {
            scanf("%d%d", &tmp, &p);
            TR.modify(tmp, p);
        } else {
            scanf("%d%d", &tmp, &p);
            TR.modify(tmp, -p);
        }
    }
    return 0;
}

ac记录(LOJ):https://loj.ac/submission/850709




xhQYm
8个月前

其实就是GCD模板,只不过是高精

高精怎么办?除了手写高精当然还可以 __int128Py

Py代码:

a=int(input()) #输入a
b=int(input()) #输入b
while (b):
    a%=b 
    a,b=b,a # 交换
print(a) #输出

时间复杂度 $O(\log n)$ ,轻松水过




xhQYm
8个月前

这是一道 tarjan 的题目。

对于题目求得两个东西,分别考虑:

  1. 其实就是求进行tarjan缩点后入度为0的点个数
  2. 入度为0的与出度为0的最大值

解释一下第一个(第二个同理,就不废话了):因为如果入度为0就意味着不会有任何学校传给他,所以第一问其实求得就是这个。

并不很难得代码:

#include<bits/stdc++.h>
#define Set(h,a) memset(h,a,sizeof h)
using namespace std;
const int N=100010,M=N<<1;
int n,m,h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,a[N],b[N];
bool in_stk[N];
int id[N],scc_cnt,Size[N];
int dout[N],din[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);  
        } 
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]); 
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            Size[scc_cnt]++; 
        }while(y!=u);
    }
}//tarjan模板
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    int tmp;
    for(int i=1;i<=n;i++)
        while(1)
        {
            scanf("%d",&tmp);
            if(!tmp) break;
            add(i,tmp),b[++m]=tmp,a[m]=i;
        }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    // Set(h,-1),Set(ne,0),Set(e,0),idx=0;
    for(int i=1;i<=m;i++)
        if(id[a[i]]!=id[b[i]])
            din[id[b[i]]]++,dout[id[a[i]]]++;
    int dinc=0,doutc=0;
    for(int i=1;i<=scc_cnt;i++)
        dinc+=(din[i]==0),doutc+=(dout[i]==0);
    if(scc_cnt==1) printf("1\n0");
    else printf("%d\n%d",dinc,max(dinc,doutc));
    return 0;
}


新鲜事 原文

xhQYm
8个月前
AC Editor 能不能调缩进格数? qwq