反思
- 暴力一定要打，T2 (O(n^6))有70分，加上二维前缀和就将近(A)掉了，可能有时候并不知道最优解，但是一定要把能拿到的分拿到
简述
T1
一道dp，设(f[i][j])为(s1,s2)分别到(i.j)位时最小距离，状态转移方程易得：
[f[i][j]=min(f[i-1][j]+k,f[i][j-1]+k,f[i-1][j-1]+dif(i,j))
]
T2
解锁了二维哈希新姿势
会的话就是板子了……
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 105
ull n;
ull a[N][N],b[N][N];
const ull base1=11,base2=13;
ull p1[N],p2[N];
void pp()
{
p1[0]=p2[0]=1;
for(int i=1;i<=n;i++)p1[i]=p1[i-1]*base1;
for(int i=1;i<=n;i++)p2[i]=p2[i-1]*base2;
}
ull get(ull aa[][N],ll x,ll y,ll h)
{
return aa[x][y]-aa[x-h][y]*p2[h]-aa[x][y-h]*p1[h]+aa[x-h][y-h]*p1[h]*p2[h];
}
map<ull,bool>mp;
ZZ_zuozhe
{
scanf("%lld",&n);
pp();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&b[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=a[i][j-1]*base1+a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=a[i-1][j]*base2+a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=b[i][j-1]*base1+b[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=b[i-1][j]*base2+b[i][j];
for(int k=0;k<=n;k++)for(int i=k;i<=n;i++)for(int j=k;j<=n;j++)mp[get(a,i,j,k)]=1;
for(int k=n;k>=0;k--)for(int i=k;i<=n;i++)for(int j=k;j<=n;j++)if(mp.find(get(b,i,j,k))!=mp.end()){printf("%d",k);return 0;}
return 0;
}
刚开始想的是二维前缀和，然后转到二维哈希发现并不会写……
其实二维前缀和+暴力比较似乎直接能(A)掉？所以以后暴力分一定要打……
T3
一个结论：对于一个数，把他分解质因数，得到(A=p_1^{a_1}cdot p_2^{a_2}cdot dots cdot p_n^{a_n})
则这个数约数总数为((a_1+1)cdot (a_2+1)cdot dots cdot (a_n+1))
所以可以用一个dfs搜索答案
注意：如果质因数指数和相同的情况下，为了使他更小，应当尽量使用更小的质因数，可以发现质因数的指数应该是单调不增的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
ll n,ans=-1,maxn=-1;
const ll p[20]={1,2,3,5,7,11,13,17,19,23,29,31};
void dfs(ll now,ll cnt,ll t,ll po)
{
if(t>maxn||(t==maxn&&now<ans))
{
ans=now;
maxn=t;
}
ll tmp=now;
for(int i=1;i<=po;i++)
{
if(tmp*p[cnt]>n)break;
tmp*=p[cnt];
if(tmp<=n)dfs(tmp,cnt+1,t*(i+1),i);
}
}
int main()
{
scanf("%lld",&n);
dfs(1,1,1,30);
printf("%lld",ans);
return 0;
}
T4
一道贪心好题
需要注意的是看出贪心的过程：如果当前必须把一个玩具放上去，如果这个玩具马上就要用了，还要把它拿下来，再把另外一个放上去……会造成很多不必要的麻烦
所以，每次需要把玩具放上去时，应当找一个再拿下来时间最晚的玩具放上去，尽量减少其对其他玩具的影响。
这里用到了(priority_queue)和(pair)，(STL)我一直都不很熟……以后得多看看，因为有时候它是真的方便……
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 500005
ll n,k,p,now,ans=0;
ll a[N],last[N],next[N];
bool vis[N];
priority_queue<pair<ll,ll> > Q;
pair<ll,ll> pt;
int main()
{
scanf("%lld%lld%lld",&n,&k,&p);
for(int i=1;i<=p;i++)scanf("%lld",&a[i]);
for(int i=1;i<=p;i++)last[a[i]]=p+1;
for(int i=p;i>=1;i--)next[i]=last[a[i]],last[a[i]]=i;
for(int i=1;i<=p;i++)
{
if(vis[a[i]])
{
k++;
Q.push(make_pair(next[i],a[i]));
}
else
{
if(!Q.empty()&&Q.size()==k)
{
pt=Q.top();
Q.pop();
vis[pt.second]=0;
}
ans++;
Q.push(make_pair(next[i],a[i]));
vis[a[i]]=1;
}
}
printf("%lld",ans);
return 0;
}