题意：给你一个日期，然后问 k 天之后日期。形式如“20240229”。保证年份在 2000 - 9999 年。
看榜的时候发现挂掉了，有点迷惑。发现思路没什么问题。把 cin，cout 改成 scanf 和 printf 就过了。
。？。什么 oj 特色。
Code
#include<bits/stdc++.h>
using namespace std;
int T;
int n,k;
int y,m,d;
int pd[10010];
int dayy[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void init(){
for(int i=2000;i<=9999;i++){
if((i%4!=0)||(i%100==0&&i%400!=0)) pd[i]=365;
else pd[i]=366;
}
}
void done(int x){
if(pd[x]==366) dayy[2]=29;
else dayy[2]=28;
}
void solve(){
y=n/10000,m=(n-y*10000)/100,d=(n-y*10000-m*100);
done(y);
int tot=d;//当前是这一天的第几天
for(int i=1;i<m;i++){
tot+=dayy[i];
}
int ay=y,am=m;
if(k>pd[y]-tot){//这一年能过完
k-=pd[y]-tot;
ay++;
while(k>pd[ay]) k-=pd[ay++];
am=1;
}
else{
if(k>dayy[am]-d){
k-=dayy[am]-d;
am++;
}
else{
cout<<n+k<<endl;
return;
}
}
done(ay);
while(k>dayy[am]) k-=dayy[am++];
printf("%d",ay);
if(am<10) cout<<"0";
printf("%d",am);
if(k<10) cout<<"0";
printf("%d\n",k);
}
int main(){
init();
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
solve();
}
return 0;
}
同学给我讲了，大概懂了思路吧。但是我不大想写，如果把同学的码直接粘过来也不大好，于是就不写了。
原：P9759 [COCI2022-2023#3] Bomboni
赛时写的爆搜。不太好意思啊部分分的暴力不会写主要是我也没咋仔细想。赛后补了一下暴力，略有一点思维吧。能拿一半分。如果 n = 1 的时候就是朴素 dp 统计，如果是小范围那就以对 H 取模来转移。每次统计这个取模的余数情况即可。
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
const int mod=998244353;
int n,H;
ll ans;
ll a[N][N],f[N][N];
ll f2[N][N][22];
void dfs(int x,int y,ll k){
if(x==n&&y==n){
if(k%H==0) ans=(ans+1)%mod;
return;
}
if(x>n||y>n) return;
if(a[x+1][y]!=-1) dfs(x+1,y,(k*a[x+1][y])%mod);
if(a[x][y+1]!=-1) dfs(x,y+1,(k*a[x][y+1])%mod);
}
void solve1(){
f[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==1&&j==1) continue;
if(a[i][j]==-1) continue;
f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
}
ans=f[n][n]%mod;
}
void solve(){
f2[1][1][a[1][1]%H]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==-1||(i==1&&j==1)) continue;
for(int k=0;k<H;k++){
int t=(k*a[i][j])%H;
f2[i][j][t]=(f2[i][j][t]+f2[i-1][j][k]+f2[i][j-1][k])%mod;
}
}
}
ans=f2[n][n][0];
}
int main(){
scanf("%d%d",&n,&H);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%lld",&a[i][j]);
}
if(a[1][1]==-1){
puts("0");
return 0;
}
if(H==1) solve1();
else if(n<=5) dfs(1,1,a[1][1]);
else solve();
cout<<ans;
return 0;
}
正解的思路和这个就比较像了。
又 T 掉了，不知道什么原因也不大想调了。几乎是对着题解抄了。这两天有点疲倦，毕竟马上 csp 了。
省流：以 gcd 转移。
预处理出来一些 gcd 防 T 掉，统计 K 的各个因数，通过这些因数转移（计算这些数和这个位置的 a[i][j] 的乘积与 K 的公因数，进一步转移）。
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=503;
const int mod=998244353;
int n,K;
int a[N][N];
int ys[2010][2010];
ll f[N][N][244];
ll ans;
int gcd(int a,int b){
if(a<2010&&b<2010&&ys[a][b]) return ys[a][b];
if(a<b) swap(a,b);
if(b) return gcd(b,a%b);
return a;
}
void init(){
for(int i=1;i<2010;i++)
for(int j=i+1;j<2010;j++) ys[i][j]=ys[j][i]=gcd(i,j);
}
vector<int> y;
int num[244],cnt;
int main(){
init();
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==-1) continue;
a[i][j]=__gcd(a[i][j],K);
}
for(int i=1;i<=K;i++){//分解因数
if(K%i==0){
y.push_back(i);
num[i]=cnt++;
}
}
f[1][1][num[a[1][1]]]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(a[i][j]==-1) continue;
for(int p=0;p<y.size();p++){
f[i][j][num[gcd(1ll*y[p]*a[i][j],K)]]=(f[i][j][num[gcd(1ll*y[p]*a[i][j],K)]]+f[i-1][j][p]+f[i][j-1][p])%mod;
}
}
printf("%lld",f[n][n][y.size()-1]);
}
赛时写的朴素暴力，获得了 10pts 的好成绩。
正解是什么，哈希+并查集维护树上启发式合并？不太想学新东西，先鸽一下吧，大概率不会填坑。
标签：10,const,22,int,31,am,2024,ll,mod From： https://www.cnblogs.com/Moyyer-suiy/p/18493664