上紫啦！
E题1:59压哨提交成功翻盘
（1:00就做完了调了一个小时，还好意思说出来？ （逃））
题面太长就不复制了，但是配图很可爱所以要贴过来
九条可怜酱好可爱呀
询问从当前时刻过多久，时间会形成回文串的形式。
暴力呀暴力
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int a,b;
int test(){
if(a/ == b% && a%==b/)return ;
return ;
}
int main(){
a=read();b=read();
for(int i=;i>=;i++){
if(test()){
printf("%d\n",i);
return ;
}
b++;
if(b>)b=,a++;
if(a>)a=;
}
return ;
}
A
扫描 前缀和
询问区间内有多少数出现次数超过K次
显然可以差分+前缀和
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int smm[mxn];
int f[mxn];
int n,K,Q;
int main(){
int i,j,a,b;
n=read();K=read();Q=read();
for(i=;i<=n;i++){
a=read();b=read();
smm[a]++;
smm[b+]--;
}
for(i=;i<=;i++){
f[i]=f[i-];
smm[i]+=smm[i-];
if(smm[i]>=K)f[i]++;
}
while(Q--){
a=read();b=read();
int ans=f[b]-f[a-];
printf("%d\n",ans);
}
return ;
}
B
贪心
可以贪心删。如果行更长就先删行再删列，否则先删列再删行。
如果删不光就是无解。
好多人没有判删顺序，全部先删行，hack了四个，233
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int stH[mxn],top1=,stL[mxn],top2=;
int mp[][];
int n,m;
void getH(){
int i,j;
for(i=;i<=n;i++){
int tmp=0x3f3f3f3f;
for(j=;j<=m;j++){
tmp=min(tmp,mp[i][j]);
}
for(j=;j<=m;j++){
mp[i][j]-=tmp;
}
while(tmp){
stH[++top1]=i;tmp--;
}
}
return;
}
void getL(){
int i,j;
for(i=;i<=m;i++){
int tmp=0x3f3f3f3f;
for(j=;j<=n;j++){
tmp=min(tmp,mp[j][i]);
}
for(j=;j<=n;j++){
mp[j][i]-=tmp;
}
while(tmp){
stL[++top2]=i;tmp--;
}
}
return;
}
void check(){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]>){
printf("-1\n");
exit();
}
}
}
return;
}
int main(){
int i,j;
n=read();m=read();
for(i=;i<=n;i++){
for(j=;j<=m;j++){
mp[i][j]=read();
}
}
if(n<=m){
getH();getL();
}
else{
getL();getH();
}
check();
printf("%d\n",top1+top2);
while(top1){
printf("row %d\n",stH[top1--]);
}
while(top2){
printf("col %d\n",stL[top2--]);
}
return ;
}
C
数学问题 找规律 组合数
手列一个表看一下，可以发现神奇的规律。
倒数第二行肯定是$k_1*a_1+k_3*a_3+k_5*a_5+..$ 和 $ k_2*a_2 + k_4 * a_4 + k_6 * a_6+..$ 的形式。
k的值和二项式系数有关
如果n%4==2，答案是前者加后者，如果n%4==0，答案是前者减后者，如果n是奇数，就先算一行，把n变成偶数。
比赛的时候没做出来，时候补题因为阶乘没加LL，WA得飞起
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int mxn=;
const int mod=1e9+;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n;
int a[mxn];
int fac[mxn],inv[mxn];
void init(){
fac[]=fac[]=inv[]=inv[]=;
for(int i=;i<mxn;i++){
fac[i]=(LL)fac[i-]*i%mod;
inv[i]=((-mod/i*(LL)inv[mod%i]%mod)+mod)%mod;
}
for(int i=;i<mxn;i++)
inv[i]=(LL)inv[i-]*inv[i]%mod;
return;
}
int C(int n,int m){
if(n<m)return ;
return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,j;
init();
n=read();
for(i=;i<=n;i++)a[i]=read();
if(n<=){
printf("%d\n",(a[]+a[])%mod);return ;
}
if(n&){
for(i=;i<n;i++){
if(i&)a[i]=(a[i]+a[i+])%mod;
else a[i]=(a[i]-a[i+]+mod)%mod;
}
n--;
}
int tmp1=,tmp2=;
int ed=n>>;
for(i=;i<=ed;i++){
tmp1=((LL)tmp1+(LL)C(ed-,i-)*a[i*-])%mod;
tmp2=((LL)tmp2+(LL)C(ed-,i-)*a[i*])%mod;
}
// printf("%d %d\n",tmp1,tmp2);
if(n%==)tmp1=((LL)(tmp1-tmp2)%mod+mod)%mod;
else tmp1=((LL)tmp1+tmp2)%mod;
printf("%d\n",tmp1);
return ;
}
D
动态规划 树形DP
$f[u][j]$表示在u结点，子树中共选了j件物品，有打折商品的最小花费
$g[u][j]$表示在u结点，子树中共选了j件物品，没有打折商品的最小花费
转移的时候，f可以加g，g不能加f，分别计算一下就可以了。
不到一个小时的时候就写完了，自信提交发现TLE。
原因是DP的时候，先加上了子树size再O(n^2)转移。
↑然而这样复杂度并不是O(n^2)的，在链数据上会被卡得超慢
↑然而一直以为是常数大，尝试了各种优化，提交了一串，无限TLE
↑在最后十几分钟冷静下来思考，终于察觉到了问题，改成先转移再加子树size，在1:59压哨提交PP
↑真™刺激
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const int mxn=;
const int INF=0x3f3f3f3f;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt;
}e[mxn<<];
int hd[mxn],mct=;
void add_edge(int u,int v){
e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;
}
int n,B;
int w[mxn],c[mxn],fa[mxn],sz[mxn];
int f[][];
int g[][];
vector<int>ve[];
int cmp(int a,int b){
return sz[a]<sz[b];
}
void DFS(int u){
f[u][]=g[u][]=;
f[u][]=w[u]-c[u];g[u][]=w[u];
sz[u]=;int tmp=;
for(int i=hd[u];i;i=e[i].nxt){
DFS(e[i].v);
ve[u].push_back(e[i].v);
tmp+=sz[e[i].v];
}
sort(ve[u].begin(),ve[u].end(),cmp);
for(register int i=;i<=tmp;i++)f[u][i]=g[u][i]=INF;
for(int i=;i<ve[u].size();i++){
int v=ve[u][i];
// sz[u]+=sz[v];
for(int j=sz[u];j>=;j--){
// int ed=min(sz[v],j);
if(j>){
for(int k=;k<=sz[v];k++){
if(f[v][k]>B && g[v][k]>B)break;
if(f[v][k]<=B)f[u][j+k]=min(f[u][j+k],f[u][j]+f[v][k]);
if(g[v][k]<=B)f[u][j+k]=min(f[u][j+k],f[u][j]+g[v][k]);
}
}
for(int k=;k<=sz[v];k++){
if(g[v][k]>B)break;
g[u][j+k]=min(g[u][j+k],g[u][j]+g[v][k]);
}
// ed=min(sz[v],j-1); }
sz[u]+=sz[v];
}
return;
}
int main(){
int i,j;
n=read();B=read();
for(i=;i<=n;i++){
w[i]=read();c[i]=read();
if(i>){
fa[i]=read();
add_edge(fa[i],i);
}
}
// memset(f,0x3f,sizeof f);
// memset(g,0x3f,sizeof g);
DFS();
int mx=;
for(i=;i<=n;i++){
if(f[][i]<=B || g[][i]<=B)mx=i;
else break;
}
printf("%d\n",mx);
/* for(i=1;i<=sz[1];i++){
printf("%d %d\n",f[1][i],g[1][i]);
}*/
return ;
}