2024杭电第一场
1012 并
考虑两维坐标都离散化后枚举每个格子，用二维前缀和计算其被覆盖的次数，设为cnt
则k固定时该格子的贡献为：( 1 - C[n-cnt][k] / C[n][k] ) * 该格子的面积
注意事项：1.处处取模 2.给的是点坐标，不是格点坐标，因此计算二维前缀和时要x++,y++
#include<bits/stdc++.h>
using namespace std;
const int N = 4e3+5;
const int mod = 998244353;
typedef long long ll;
int n;
int sum[N][N],tot[N];
ll f[N][N];
map<int,int>xid,yid;
struct tringle{
int x,y,x2,y2;
void deal(){
x=xid[x],x2=xid[x2];
y=yid[y],y2=yid[y2];
x++,y++;
sum[x][y]++;
sum[x][y2+1]--;
sum[x2+1][y]--;
sum[x2+1][y2+1]++;
}
}t[N];
int x[N*2],y[N*2];
int qpow(ll a,ll b){
ll ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
int inv(int x){
return qpow(x,mod-2);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
f[0][0]=1;
for(int i=1;i<N;i++){
f[i][0]=1;
for(int j=1;j<=i;j++)
f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
cin>>n;
int cntx=0,cnty=0;
for(int i=1;i<=n;i++){
cin>>t[i].x>>t[i].y>>t[i].x2>>t[i].y2;
x[++cntx]=t[i].x;x[++cntx]=t[i].x2;
y[++cnty]=t[i].y;y[++cnty]=t[i].y2;
}
sort(x+1,x+cntx+1);
sort(y+1,y+cnty+1);
cntx=unique(x+1,x+cntx+1)-(x+1);
cnty=unique(y+1,y+cnty+1)-(y+1);
for(int i=1;i<=cntx;i++){
xid[x[i]]=lower_bound(x+1,x+cntx+1,x[i])-(x);
// cout<<x[i]<<" "<<xid[x[i]]<<"\n";
}
for(int i=1;i<=cnty;i++){
yid[y[i]]=lower_bound(y+1,y+cnty+1,y[i])-(y);
// cout<<y[i]<<" "<<yid[y[i]]<<"\n";
}
for(int i=1;i<=n;i++)
t[i].deal();
for(int i=1;i<=cntx;i++){
for(int j=1;j<=cnty;j++){
int tmp=(sum[i-1][j]+sum[i][j-1])%mod;
tmp=(tmp-sum[i-1][j-1]+mod)%mod;
sum[i][j]+=tmp;
sum[i][j]%=mod;
tot[sum[i][j]]+=1ll*(x[i]-x[i-1])*(y[j]-y[j-1])%mod;
tot[sum[i][j]]%=mod;
}
}
ll ans[n+5]={0};
for(int k=1;k<=n;k++){
int inv_c_n_k=inv(f[n][k]);
for(int cnt=1;cnt<=n;cnt++){
ll tmp=(1-1ll*f[n-cnt][k]*inv_c_n_k%mod+mod)%mod;
tmp=tmp*tot[cnt]%mod;
ans[k]=(ans[k]+tmp)%mod;
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
}
1001
处理出每个循环串的哈希值丢到一个map里，在大串中查询[ i-len,i ]的哈希值是否在map中出现过，是则+1
不要被骗去写后缀自动机了，这题空间给的很小
#include<bits/stdc++.h>
using namespace std;
const int N = 1048576*2;
const int base=13331;
typedef unsigned long long ull;
ull z[N],p[N],f[N];
ull get1(int l,int r){
return z[r]-z[l-1]*p[r-l+1];
}
ull get2(int l,int r){
return f[r]-f[l-1]*p[r-l+1];
}
void solve(){
map<ull,int>mp;
string s,t;cin>>s>>t;
s=s+s;
s=" "+s;
p[0]=1;
int n=s.length();
n--;
for(int i=1; i<=n; i++)
{
z[i]=z[i-1]*base-s[i]-'a'+1;
p[i]=p[i-1]*base;
}
t=" "+t;
int m=t.length();
m--;
for(int i=1; i<=m; i++)
{
f[i]=f[i-1]*base-t[i]-'a'+1;
}
int ans=0;
for(int i=1;i<=n/2;i++){
mp[get1(i,i+n/2-1)]=1;
}
for(int j=n/2;j<=m;j++){
if(mp[get2(j-n/2+1,j)]) ans++;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--){
//TODO
solve();
}
}
1002
暴力dp就可以
正解是 nsqrt(k) 的做法，考虑把读入的数据随机打乱，则在第i格预计的期望是 k/n*i，在这个范围附近找即可，但步长没看懂为什么是v*sqrt(k)
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
typedef long long ll;
ll dp[N*4],a[N],b[N],c[N],d[N];
void solve(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) {
cin>>a[i]>>b[i]>>c[i]>>d[i];
}
dp[0]=0;
for(int j=1;j<=k;j++) dp[j]=1e16;
// cout<<666<<"\n";
for(int i=1;i<=n;i++){
for(int j=k;j>=1;j--){
if(j>=1) dp[j]=min(dp[j],dp[j-1]+a[i]);
if(j>=2) dp[j]=min(dp[j],dp[j-2]+b[i]);
if(j>=3) dp[j]=min(dp[j],dp[j-3]+c[i]);
if(j>=4) dp[j]=min(dp[j],dp[j-4]+d[i]);
// cout<<i<<" "<<j<<" "<<dp[j]<<"\n";
}
}
cout<<dp[k]<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--){
//TODO
solve();
}
}
1008
队友做的
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int K=15,N=1<<K;
int n,k,ans;
inline int read()
{
int x=0;bool f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return f?x:-x;
}
void Kafka()
{
n=read(),k=read();
ans=1;
for(int i=0;i<k;++i)
{
int res=0;
if(n&(1<<i)) res=12;
else res=4;
ans*=res;
}
cout<<ans<<endl;
}
signed main()
{
for(int T=read();T--;)Kafka();
return 0;
}