The 2018 ICPC Asia Shenyang Regional Contest [Cloned]
A-Sockpuppets
B-Sequences Generator
C-Insertion Sort
题意：
多组样例，给你一个长度为n的数组，以及前k个数能进行升序排序，一个模数q，问有多少中方案能形成最长上升子序列>=n-1
solution：
1、k==1时，将按1，2，3，4，5这样n个数有序的单独拎出来作为一种方法，然后就是n-1个数是上升的，对于每一个数，他都能放在除了原来的位置之外的n-1个位置，所以有n(n-1)中方法，但是里面有重复，经过找规律发现相邻两个数会出现一个重复的方法，因此要减去n-1
最终答案为(n-1)(n-1)+1
2、k>1,若k>=n,那么k=n(因为此时这n个数可以任意排序)，对于前k个数可以任意排序，所以为k!,之后按1-k k+1-n单独拎出来，那么就会有k!种方案，若是将前(k-1)个数中的一个与k+1交换，然后那个交换的数就能放在后面n-k个位置的任意一个位置，此时k!(k-1)(n-k),将第k个数拎出来，那么就类似k=1时的操作，此时方案数为k!(n-k)(n-k)
最终答案为：k!(n-1)(n-k)+k!
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int t;
int main()
{
scanf("%d",&t);
for(int c=1;c<=t;c++)
{
ll res=1;
ll n,k,q;scanf("%lld%lld%lld",&n,&k,&q);
if(k==1)
res=((n-1)*(n-1)%q+1)%q;
else
{
if(k>=n)k=n;
for(int i=1;i<=k;i++)
res=res*i%q;
res=res*((n-1)*(n-k)%q+1)%q;
}
printf("Case #%d: %lld\n",c,res);
}
}
D-Diameter of a Tree
E-The Kouga Ninja Scrolls
F-Counting Sheep in Ami Dongsuo
G-Best ACMer Solves the Hardest Problem
题意：
t组样例，n个点，m次操作，给你n个点的坐标，以及该点上的点权。
m次操作为
1 x y w 向（x,y）中插入一个点权为w的点
2 x y 将（x,y）删除
3 x y k w 向以(x,y)为圆心，根号k为半径的整数点上加上权值w
4 x y k 求以（x,y）为圆心，根号k为半径的整数点上的权值之和
对于这些操作的坐标（x,y）都是在原来的基础上加上lastans而来的，x=(x+lastans)%6000+1，y=(y+lastans)%6000+1。lastans的初始值为0，在每执行过一次操作4后，lastans的值变为操作4输出的值。
tips：
如果一些坐标的点没有插入，那么该点无法在3操作的基础上加上权值w，题目保证插入的点在之前并不存在，删除的点在之前已经存在。初始给的n个点不用加lastans
solution：
k的范围在6000之内，所以以根号k为半径的整数点肯定不会超过一百。所以可以暴力更新以(x,y)为圆心的点。
主要是数据的初始化需要存下来，不然暴力初始化会tle
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int n,m,t;
ll vis[6060][6060];
const int mod=6000;
ll last=0;
vector<P> e[10000010];
int main()
{
memset(vis,0,sizeof(vis));
for(int i=0;i<=6000;i++)
{
for(int j=0;j<=6000;j++)
{
if(i*i+j*j>10000000)break;
e[i*i+j*j].push_back(P(i,j));
if(i!=0)e[i*i+j*j].push_back(P(-i,j));
if(j!=0)e[i*i+j*j].push_back(P(i,-j));
if(j!=0&&i!=0)e[i*i+j*j].push_back(P(-i,-j));
}
}
scanf("%d",&t);
for(int c=1;c<=t;c++)
{
printf("Case #%d:\n",c);
set<P> st;
last=0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
int x,y,w;scanf("%d%d%d",&x,&y,&w);
vis[x][y]=w;
st.insert(P(x,y));
}
while(m--)
{
ll op,x,y,k;
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&k);
x=((x+last)%mod)+1;
y=((y+last)%mod)+1;
st.insert(P(x,y));
vis[x][y]=k;
}
else if(op==2)
{
scanf("%lld%lld",&x,&y);
x=((x+last)%mod)+1;
y=((y+last)%mod)+1;
vis[x][y]=0;
}
else if(op==3)
{
int w;
scanf("%lld%lld%lld%lld",&x,&y,&k,&w);
x=((x+last)%mod)+1;
y=((y+last)%mod)+1;
for(int i=0;i<e[k].size();i++)
{
int xx=e[k][i].first+x,yy=e[k][i].second+y;
if(xx<1||xx>mod||yy<1||yy>mod)continue;
if(vis[xx][yy])vis[xx][yy]+=w;
}
}
else
{
scanf("%lld%lld%lld",&x,&y,&k);
x=((x+last)%mod)+1;
y=((y+last)%mod)+1;
ll sum=0;
for(int i=0;i<e[k].size();i++)
{
int xx=e[k][i].first+x,yy=e[k][i].second+y;
if(xx<1||xx>mod||yy<1||yy>mod)continue;
if(vis[xx][yy])sum+=vis[xx][yy];
}
printf("%lld\n",sum);
last=sum%mod;
}
}
for(auto it:st)vis[it.first][it.second]=0;
st.clear();
}
}
京公网安备 11010502036488号