2024“钉耙编程”中国大学生算法设计超级联赛（1）结题报告1 2 8

#include<bits/stdc++.h>
using namespace std;
// 22222
const int N = 5e6 + 10;
const int p1 = 1e9 + 7, base1 = 13331;
const int p2 = 998244353, base2 = 100153;

int n, m;
int ha1[N], ha2[N], hb1[N], hb2[N];
int c1[N], c2[N];

// 计算哈希函数
void compute_hashes(const string& str, int len) {
    c1[0] = c2[0] = 1;
    for (int i = 1; i <= len; i++) {
        c1[i] = (1LL * c1[i - 1] * base1) % p1;
        c2[i] = (1LL * c2[i - 1] * base2) % p2;
    }

    ha1[0] = ha2[0] = 0;
    for (int i = 1; i <= len; i++) {
        ha1[i] = (1LL * ha1[i - 1] * base1 + (str[i - 1] - 'A' + 1)) % p1;
        ha2[i] = (1LL * ha2[i - 1] * base2 + (str[i - 1] - 'A' + 1)) % p2;
    }
}

// 获取字符串 l 到 r 的哈希值
pair<int, int> get_hash(int l, int r) {
    int hash_value1 = (ha1[r] - 1LL * ha1[l - 1] * c1[r - l + 1] % p1 + p1) % p1;
    int hash_value2 = (ha2[r] - 1LL * ha2[l - 1] * c2[r - l + 1] % p2 + p2) % p2;
    return { hash_value1, hash_value2 };
}

void solve() {
    string a, b;
    cin >> a >> b;
    int len_a = a.size();
    int len_b = b.size();

    string a_twice = a + a;
    compute_hashes(a_twice, len_a * 2);

    set<pair<int, int>> hash_set;
    for (int i = 0; i < len_a; i++) {
        hash_set.insert(get_hash(i + 1, i + len_a));
    }

    compute_hashes(b, len_b);
    int ans = 0;
    for (int i = 0; i + len_a <= len_b; i++) {
        auto hash_b = get_hash(i + 1, i + len_a);
        if (hash_set.count(hash_b)) {
            ans++;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
}

#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n+1),b(n+1),c(n+1),d(n+1);
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i]>>d[i];
    vector<int>dp(k+1,1e18);
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=min(i*4,k);j>=0;j--){
            if(j>=4)dp[j]=min(dp[j-4]+d[i],dp[j]);
            if(j>=3)dp[j]=min(dp[j-3]+c[i],dp[j]);
            if(j>=2)dp[j]=min(dp[j-2]+b[i],dp[j]);
            if(j>=1)dp[j]=min(dp[j-1]+a[i],dp[j]);
        }
    }
    cout<<dp[k]<<'\n';
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--)solve();
}

#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
const int N=4e4+10;
int dp[N];
int ndp[N],sum[N];
int n,k;
void init(){
    for(int i=0;i<(1<<k);i++){
        ndp[i]=dp[i];
        dp[i]=0;
    };
}
void solve(){
    int ans=0;
    cin>>n>>k;
    int nw=1ll;
    for(int i=0;i<k;i++){
        int res=0;
        for(int a=0;a<2;a++){
            for(int b=0;b<2;b++){
                for(int c=0;c<2;c++){
                    for(int d=0;d<2;d++){
                        if((((a&b)^c)|d)==(n>>i&1))res++;
                    }
                }
            }
        }
        nw*=res;
    }
    cout<<nw<<'\n';
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--)solve();
}