2024“钉耙编程”中国大学生算法设计超级联赛（1）

Rank

待补1003树，1005博弈，1012并。

星星 - HDU 7434 - Virtual Judge

这题第一眼云的时候感觉是贪心，后来要上手写代码感觉无从下手，遂反映过来是动态规划。

然后就是一个很简单的dp，外层枚举物品，里面枚举价值。

#include<bits/stdc++.h>
using ll=long long;
using PII=std::pair<double,double>;

#define fir first
#define sec second

const int N=2e3+10;

int a[N][10];
double b[N][10],c[N]; 
int f[N][N];
void solve()
{
    int n,k;
    std::cin>>n>>k;//获得k个星星的最小代价 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=4;j++) 
        {
            std::cin>>a[i][j];
        }
    }
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    
    for(int p=1;p<=n;p++)
    {
            for(int i=0;i<=k;i++)//星星数目 
            {    
                f[p][i]=f[p-1][i];
                for(int j=0;j<5;j++)
                {
                    if(i>=j) 
                    {
                        f[p][i]=std::min(f[p-1][i-j]+a[p][j],f[p][i]);
                    }
                }
            }
    }
    std::cout<<f[n][k];
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    int t=1;
    std::cin>>t;
    while(t--)
    {
        solve();
    } 
    return 0;
}

 位运算 - HDU 7440 - Virtual Judge (vjudge.net)

因为位运算是按照每一位来计算，所以第一反应是根据表达式推结果为1的时候有多少种情况，那么情况总数就是每一位的情况数相乘。

，然后根据这个式子，随便推一推。

然后就想题目给k是什么意思，呃原来是abcd的范围是[0,2^k)，那也就是说这四个数最大k位呗。直接枚举每一位，如果n当前是1就乘上12，否则乘4，然后右移即可。

#include<bits/stdc++.h>
using ll=long long;
using PII=std::pair<double,double>;

#define fir first
#define sec second

const int N=2e3+10;

int a[N][10];
void solve()
{
    int n,k;
    std::cin>>n>>k;
    ll cnt=1;
    for(int i=1;i<=k;i++)
    {
        if(n&1) cnt*=12;
        else cnt*=4;
        
        n>>=1;
    }
    std::cout<<cnt<<'\n';
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    int t=1;
    std::cin>>t;
    while(t--)
    {
        solve();
    } 
    return 0;
}

循环位移 - HDU 7433 - Virtual Judge

看懂题之后就知道，a是小串，要找出b中有多少个子串在a+a中出现过。

然后要做的就是字符串哈希，亲测这题STL会TLE，所以以后比赛都尽量手写哈希吧。

思路：对a+a中所有长为lena的字符串求哈希值，然后存进map里面。然后对b中所有长为lena的字符串求哈希值，如果在map中出现过就cnt++。然后就是ull自然溢出。（今天才知道map<string,int>是O(N)的，ull才是O1。

#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
using PII=std::pair<double,double>;

#define fir first
#define sec second

const int N=1068576,P=131;

#define int ull
ull h[N],p[N],h1[N];
void init()
{
    p[0]=1;
    for(int i=1;i<=N;i++)
    {
        p[i]=p[i-1]*P;
    }
}
ull get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
ull get1(int l,int r)
{
    return h1[r]-h1[l-1]*p[r-l+1];
}
void solve()
{
    std::string a,b;
    std::cin>>a>>b;
    
    int lena=a.length();
    int lenb=b.length();
    
    a=' '+a+a;
    b=' '+b;
    
    std::map<ull,int> mp;
    for(int i=1;i<a.length();i++)
    {
        h[i]=h[i-1]*P+a[i];
    }
    for(int i=1;i+lena-1<a.length();i++)
    {
        mp[get(i,i+lena-1)]=1;
    }
    
    for(int i=1;i<b.length();i++)
    {
        h1[i]=h1[i-1]*P+b[i];
    }
    
    ll cnt=0;
    for(int i=1;i+lena-1<b.length();i++)
    {
        if(mp[get1(i,i+lena-1)]) cnt++;
    }
    std::cout<<cnt<<'\n';
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    init();
    
    int t=1;
    std::cin>>t;
    while(t--)
    {
        solve();
    } 
    return 0;
}