C.Insertion Sort
题意：Q次询问，每次给出N，M，Mod，问你有多少种排列，满足前面M个数字排序之后整个序列的LIS>=N-1。
思路：我们把数字看成[1,M]，[N-M+1,N]两个部分，假设是A和B。分几种情况即可。
我发现我好像想错了。 https://blog.csdn.net/qq_23502651/article/details/84680151
另外：长度为N的排列的LIS为N-1的个数=(N-1)^2； 可以推出这个公式。F(i)=F(i-1)+i-1; F(2)=1; F(3)=F(2)+2...就有了.
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int main()
{
ll T,N,M,C=,Mod,ans;
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&N,&M,&Mod);
if(M>=N-){
ans=;
rep(i,,N) ans=(ll)ans*i%Mod;
}
else {
ans=; ll t=((N-M)*(N-M-)+M*(N-M)+)%Mod;
rep(i,,M) ans=(ll)ans*i%Mod;
ans=(ll)ans*t%Mod;
}
printf("Case #%lld: %lld\n",++C,ans);
}
return ;
}
E .The Kouga Ninja Scrolls
题意：二维平面上有一些点，现在又几种操作，修改点的位置，修改点的颜色。 询问区间异色的点在最远曼哈顿距离。
思路：最远曼哈顿距离，想到转化为切比雪夫距离，然后线段树。以为要维护最大次大，最小次小，x，y； 感觉太多太长没敢写。
我们可以不转化为切比雪夫，直接用之前的k维最远距离，建立2^k棵线段树。 这样的好处是。 一个区间的最小值，等效与补值对应的线段树的最大值的相反数。
这样我们就没必要维护最小次小了，代码会好看一点。
本题收获：最大和最小值，我们可以统一； 在合并的情况比较多的时候，开一些全局变量，然后减少情况讨论。 比如query的时候，直接与全局变量的res更新答案。
好麻烦啊。。。估计转化维切比雪夫的代码会很长。
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<ll,ll>
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=;
const ll inf=(1LL<<);
ll x[maxn],y[maxn],a[maxn][];int c[maxn];
pii res[][];
struct in{
pii Mx[maxn<<][]; int idx;
void pushup(int Now)
{
if(Mx[Now<<][].s!=Mx[Now<<|][].s){
if(Mx[Now<<][].f>Mx[Now<<|][].f){
Mx[Now][]=Mx[Now<<][];
Mx[Now][]=max(Mx[Now<<][],Mx[Now<<|][]);
}
else {
Mx[Now][]=Mx[Now<<|][];
Mx[Now][]=max(Mx[Now<<|][],Mx[Now<<][]);
}
}
else {
rep(i,,)
Mx[Now][i]=max(Mx[Now<<][i],Mx[Now<<|][i]);
}
}
void build(int Now,int L,int R)
{
if(L==R){
Mx[Now][].f=a[L][idx]; Mx[Now][].s=c[L];
Mx[Now][].f=-inf; Mx[Now][].s=-;
return ;
}
int Mid=(L+R)>>;
build(Now<<,L,Mid);
build(Now<<|,Mid+,R);
pushup(Now);
}
void update(int Now,int L,int R,int pos)
{
if(L==R){
Mx[Now][].f=a[L][idx]; Mx[Now][].s=c[L];
Mx[Now][].f=-inf; Mx[Now][].s=-;
return ;
}
int Mid=(L+R)>>;
if(pos<=Mid) update(Now<<,L,Mid,pos);
else update(Now<<|,Mid+,R,pos);
pushup(Now);
}
void query(int Now,int L,int R,int l,int r)
{
if(l<=L&&r>=R){
if(Mx[Now][].s!=res[idx][].s){
if(Mx[Now][].f>res[idx][].f){
res[idx][]=max(res[idx][],Mx[Now][]);
res[idx][]=Mx[Now][];
}
else {
res[idx][]=max(res[idx][],Mx[Now][]);
}
}
else {
rep(i,,)
res[idx][i]=max(res[idx][i],Mx[Now][i]);
}
return ;
}
int Mid=(L+R)>>;
if(l<=Mid) query(Now<<,L,Mid,l,r);
if(r>Mid) query(Now<<|,Mid+,R,l,r);
}
}T[];
int main()
{
int Cas,N,M,Fcy=,opt,L,R,K,C;ll X,Y;
scanf("%d",&Cas); rep(i,,) T[i].idx=i;
while(Cas--){
scanf("%d%d",&N,&M);
rep(i,,N) scanf("%I64d%I64d%I64d",&x[i],&y[i],&c[i]);
rep(i,,N) {
a[i][]=x[i]+y[i];
a[i][]=x[i]-y[i];
a[i][]=-x[i]+y[i];
a[i][]=-x[i]-y[i];
}
rep(i,,) T[i].build(,,N);
printf("Case #%d:\n",++Fcy);
while(M--){
scanf("%d",&opt);
if(opt==){
scanf("%d%I64d%I64d",&K,&X,&Y);
x[K]+=X; y[K]+=Y;
a[K][]=x[K]+y[K];
a[K][]=x[K]-y[K];
a[K][]=-x[K]+y[K];
a[K][]=-x[K]-y[K];
rep(j,,) T[j].update(,,N,K);
}
else if(opt==){
scanf("%d%d",&K,&C); c[K]=C;
rep(i,,) T[i].update(,,N,K);
}
else {
scanf("%d%d",&L,&R);
rep(i,,) {
res[i][].f=res[i][].f=-inf;//mp(-inf,-1);
res[i][].s=res[i][].s=-;
}
rep(i,,) T[i].query(,,N,L,R);
ll ans=;
rep(i,,) {
if(res[i][].s!=res[-i][].s) ans=max(ans,res[i][].f+res[-i][].f);
else {
ans=max(ans,res[i][].f+res[-i][].f);
ans=max(ans,res[i][].f+res[-i][].f);
}
}
printf("%I64d\n",ans);
}
}
}
return ;
}
G .Best ACMer Solves the Hardest Problem
题意：在二维平面上四种操作： 1，加一个带权的点； 2，删去一个点； 3，给一个点周围欧几里得距离为sqrt(k)的存在的点点权都加w； 4，查询一个到点欧几里得距离为sqrtk的点权和。
思路：发现到一个点的欧几里得距离为k的点并不多。所以我们暴力即可。 注意用 ll。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxm=;
const int maxn=;
ll a[maxn][maxn];int vis[maxn][maxn],Ca,tot;
vector<pii>G[maxm+];
void init()
{
rep(i,,){
rep(j,,){
if(i*i+j*j>maxm) break;
G[i*i+j*j].push_back(mp(i,j));
tot++;
}
}
}
void add(int x,int y,int w)
{
if(vis[x][y]!=Ca) a[x][y]=,vis[x][y]=Ca;
a[x][y]+=w;
}
void del(int x,int y)
{
vis[x][y]=; a[x][y]=;
}
void FCY(int x,int y,int w)
{
if(x<||x>||y<||y>) return ;
if(vis[x][y]==Ca) a[x][y]+=w;
}
int query(int x,int y)
{
if(x<||x>||y<||y>) return ;
if(vis[x][y]==Ca) return a[x][y];
return ;
}
void ADD(int x,int y,int k,int w)
{
for(int i=;i<G[k].size();i++){
int dx=G[k][i].first,dy=G[k][i].second;
FCY(x+dx,y+dy,w);
if(dx!=) FCY(x-dx,y+dy,w);
if(dy!=) FCY(x+dx,y-dy,w);
if(dx!=&&dy!=) FCY(x-dx,y-dy,w);
}
}
ll Query(int x,int y,int k)
{
ll res=;
for(int i=;i<G[k].size();i++){
int dx=G[k][i].first,dy=G[k][i].second;
res+=query(x+dx,y+dy);
if(dx!=) res+=query(x-dx,y+dy);
if(dy!=) res+=query(x+dx,y-dy);
if(dx!=&&dy!=) res+=query(x-dx,y-dy);
} return res;
}
int main()
{
int T,N,M,x,y,w,k,opt;ll ans;
init();
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M); Ca++; ans=;
printf("Case #%d:\n",Ca);
rep(i,,N){
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
rep(i,,M){
scanf("%d%d%d",&opt,&x,&y);
x=(x+ans)%+; y=(y+ans)%+;
if(opt==){
scanf("%d",&w);
add(x,y,w);
}
else if(opt==){
del(x,y);
}
else if(opt==){
scanf("%d%d",&k,&w);
ADD(x,y,k,w);
}
else {
scanf("%d",&k);
printf("%lld\n",ans=Query(x,y,k));
}
}
}
return ;
}
K .Let the Flames Begin
题意：约瑟夫问题，给定N，K，M，问第M个出来的人的编号是。 K或者M<1e6；
思路：只要知道公式就大概知道怎么做的题。
我们知道第N个人出来的编号公式是： p=0 ; rep(i,1,N) p=(p+k)%i; ans=p;（假设从0开始）
而第M个出来的人的编号，我们可以假设已经进行了N-M轮，但其实我们并不关心他们的位置，我可以做完之后把他们放到对应位置即可。
所以第M个人的编号是：p=0；rep(i,1,M) p=(p+k)%(i+N-M);
当M比较小时，可以直接求； 当K比较小时，我们可以利用整除合并的思想做。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
using namespace std;
ll solve(ll N,ll M,ll K) //N个人，每K个skip一次，第M次skip的是谁
{
if(K==) return M; ll p=;
if(M<=K){
rep(i,,M){
p=(p+K-)%(i+N-M)+;
}
}
else {
ll tM=M;
rep(i,,M){
if(!tM) break;
if(p+K->=i+N-M) tM--,p=(p+K-)%(i+N-M)+;//,cout<<i<<":"<<p<<endl;
else {
//p+kx-1<i+x-1+N-M -> x<(i-1+N-M-p)/(k-1);
ll t=(i+N-M-p)/(K-),g;
if((i+N-M-p)%(K-)==) t--;
g=min(t,tM);
p=p+K*g; tM-=g;
i=i+g-;
}
}
}
return p;
}
int main()
{
int T,Ca=; ll N,M,K;
scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld",&N,&M,&K);
printf("Case #%d: %lld\n",++Ca,solve(N,M,K));
}
return ;
}
J .How Much Memory Your Code Is Using?
题意：开了一些变量，问你用了多少内存。
思路：模拟即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const int mod=1e9+;
char c[],a[]={'l','o','n','g',' ','l','o','n','g'};
char b[]={'l','o','n','g',' ','d','o','u','b','l','e'};
ll sum=; int L;
bool check1()
{
bool F=true;
if(L<) return false;
rep(i,,) if(c[i]!=a[i]) return false;
return true;
}
bool check2()
{
bool F=true;
if(L<) return false;
rep(i,,) if(c[i]!=b[i]) return false;
return true;
}
void solve()
{
ll tmp; L=strlen(c);
if(c[]=='b'||c[]=='c') tmp=;
if(c[]=='i'||c[]=='f') tmp=;
if(check1()||c[]=='d') tmp=;
if(c[]=='_'||check2()) tmp=;
rep(i,,L-){
if(c[i]=='['){
int k=;
rep(j,i+,L-) if(c[j]>=''&&c[j]<='') k=k*+c[j]-'';
tmp*=k;
break;
}
}
sum+=tmp;
}
int main()
{
int T,N,Ca=;
scanf("%d",&T);
while(T--){
scanf("%d\n",&N); sum=;
rep(i,,N){
gets(c);
solve();
}
ll F=sum/; if(sum%) F++;
printf("Case #%d: %lld\n",++Ca,F);
}
return ;
}