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;
}
原文地址：https://blog.csdn.net/m0_74183164/article/details/140559004
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！