| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 7/13 | . | . | O | . | . | . | O | . | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A Sockpuppets
题目描述
解题思路
AC代码
2
B Sequences Generator
题目描述
解题思路
AC代码
2
C Insertion Sort
题目描述
求插入排序$k$轮，最后得到的序列是$almost\space sorted$序列的序列种数。
解题思路
插入排序$k$轮保证了前$k$位有序，故枚举所有$almost\space sorted$序列，则原序列前$k$个元素必然为前$1-k$或$1-k$中的$k-1$个元素加一个后面的数字。当前$k$个元素为$1-k$时，后半段产生一对插入错误的数，即除掉有序数列的$almost\space sorted\space array$，种数为$(n-k-1)^2$。否则必然为取$1-（k-1）$中某个元素放到后面的第一个位置，后面选$n-k$个元素中的某个元素放到前面，共有$k\times (n-k)$种方法。此外，对于数$k$，可以与后面的任何数交换，交换后仍保证几乎排序，故需要再加$n-k-1$。以上只枚举了有一个错位的情况，还需要加一个有序排列。前$k$个元素全排列，再乘一个$k!$即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
using namespace std;
int main(){
int i,T,Cas=0;
scanf("%d",&T);
while(T--){
int n,k,mod;
scanf("%d%d%d",&n,&k,&mod);k=min(n,k);
ll ans=1ll*(n-k)*(n-k-1)+1ll*k*(n-k)+1;
ans%=mod;
for(i=1;i<=k;i++)ans=ans*i%mod;
printf("Case #%d: %lld\n",++Cas,ans);
}
return 0;
}
D Diameter of a Tree
题目描述
解题思路
AC代码
2
E The Kouga Ninja Scrolls
题目描述
解题思路
AC代码
2
F Counting Sheep in Ami Dongsuo
题目描述
解题思路
AC代码
2
G Best ACMer Solves the Hardest Problem
题目描述
有一个平面，上面有一些有权值的点。有四种操作：
- 在$(x,y)$处插入一个权值为为$w$的点，保证操作前这个坐标上不存在点；
- 删除$(x,y)$处的点；
- 将与$(x,y)$之间欧几里得距离为$\sqrt k$的所有点权值$+w$；
- 求与$(x,y)$之间欧几里得距离为$\sqrt k$的所有点权值之和。
解题思路
由于$x^2+y^2=k$的$(x,y)$较少，可以预处理一下暴力修改，特判$\Delta x=0$或$\Delta y=0$的情况。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
typedef long long ll;
using namespace std;
vector<pair<int,int>>pos[P];
int v[N][N],x[P],y[P];
int jud(int x,int y){
return x>=1&&x<=6000&&y>=1&&y<=6000&&v[x][y];
}
int main(){
int i,j,n,m,T,Cas=0;
for(i=0;i<=6000;i++){
for(j=0;j<=6000;j++){
if(i*i+j*j<P)pos[i*i+j*j].push_back(make_pair(i,j));
else break;
}
}
scanf("%d",&T);
while(T--){
printf("Case #%d:\n",++Cas);
scanf("%d%d",&n,&m);
int val,X,Y;
for(i=1;i<=n;i++)scanf("%d%d%d",&x[i],&y[i],&val),v[x[i]][y[i]]=val;
ll lastans=0;
int opt,k;
while(m--){
scanf("%d",&opt);
scanf("%d%d",&X,&Y);
X=(X+lastans)%6000+1;
Y=(Y+lastans)%6000+1;
if(opt==1){
scanf("%d",&val);
x[++n]=X;y[n]=Y;
v[X][Y]=val;
}else if(opt==2){
v[X][Y]=0;
}else if(opt==3){
scanf("%d%d",&k,&val);
for(auto j:pos[k]){
if(!j.first&&!j.second){
if(jud(X+j.first,Y+j.second))v[X+j.first][Y+j.second]+=val;
}else if(!j.first){
if(jud(X+j.first,Y+j.second))v[X+j.first][Y+j.second]+=val;
if(jud(X+j.first,Y-j.second))v[X+j.first][Y-j.second]+=val;
}else if(!j.second){
if(jud(X+j.first,Y+j.second))v[X+j.first][Y+j.second]+=val;
if(jud(X-j.first,Y+j.second))v[X-j.first][Y+j.second]+=val;
}else{
if(jud(X+j.first,Y+j.second))v[X+j.first][Y+j.second]+=val;
if(jud(X+j.first,Y-j.second))v[X+j.first][Y-j.second]+=val;
if(jud(X-j.first,Y+j.second))v[X-j.first][Y+j.second]+=val;
if(jud(X-j.first,Y-j.second))v[X-j.first][Y-j.second]+=val;
}
}
}else{
ll ans=0;
scanf("%d",&k);
for(auto j:pos[k]){
if(!j.first&&!j.second){
if(jud(X+j.first,Y+j.second))ans+=v[X+j.first][Y+j.second];
}else if(!j.first){
if(jud(X+j.first,Y+j.second))ans+=v[X+j.first][Y+j.second];
if(jud(X+j.first,Y-j.second))ans+=v[X+j.first][Y-j.second];
}else if(!j.second){
if(jud(X+j.first,Y+j.second))ans+=v[X+j.first][Y+j.second];
if(jud(X-j.first,Y+j.second))ans+=v[X-j.first][Y+j.second];
}else{
if(jud(X+j.first,Y+j.second))ans+=v[X+j.first][Y+j.second];
if(jud(X+j.first,Y-j.second))ans+=v[X+j.first][Y-j.second];
if(jud(X-j.first,Y+j.second))ans+=v[X-j.first][Y+j.second];
if(jud(X-j.first,Y-j.second))ans+=v[X-j.first][Y-j.second];
}
}
printf("%lld\n",ans);
lastans=ans;
}
}
for(i=1;i<=n;i++)v[x[i]][y[i]]=0;
}
return 0;
}
H Rainbow Graph
题目描述
解题思路
AC代码
2
I Distance Between Sweethearts
题目描述
有六个整数变量$I_{girl},U_{girl},A_{girl},I_{boy},U_{boy},A_{boy}$。分别给定他们的上限（均为$\leq 2000$的正整数），它们的下限为$0$。
求所有在合法区间内的$max(|I_{girl}-I_{boy}|,|U_{girl}-U_{boy}|,|A_{girl}-A_{boy}|)\oplus I_{girl}\oplus U_{girl}\oplus A_{girl}\oplus I_{boy}\oplus U_{boy}\oplus A_{boy}$之和。
解题思路
从小到大枚举绝对值里面的东西，分别将绝对值符合要求的对应异或值存到三个数组里，累计求和即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
typedef unsigned long long ull;
using namespace std;
int u[N],v[N],w[N];
ull f[M][2],g[M][2],h[M][2];
//x对应位数种数，y对应位数种数，xy元素异或对应种数
void solve(int *x,int *y){
memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(h,0,sizeof(h));
int i,j,k;
for(i=0;i<N;i++){
if(x[i])for(j=0;j<M;j++)f[j][!!((1<<j)&i)]+=x[i];
if(y[i])for(j=0;j<M;j++)g[j][!!((1<<j)&i)]+=y[i];
}
for(i=0;i<M;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
h[i][j^k]+=(1ll<<i)*f[i][j]*g[i][k];
}
int main(){
int i,j,k,T,Cas=0;
scanf("%d",&T);
while(T--){
ull ans=0;
vector<int>vu[N],vv[N],vw[N];
for(i=0;i<N;i++){
vu[i].clear(),vv[i].clear(),vw[i].clear();
u[i]=v[i]=w[i]=0;
}
int u0,u1,v0,v1,w0,w1;
scanf("%d%d%d%d%d%d",&u0,&v0,&w0,&u1,&v1,&w1);
for(i=0;i<=u0;i++)for(j=0;j<=u1;j++)vu[abs(i-j)].push_back(i^j);
for(i=0;i<=v0;i++)for(j=0;j<=v1;j++)vv[abs(i-j)].push_back(i^j);
for(i=0;i<=w0;i++)for(j=0;j<=w1;j++)vw[abs(i-j)].push_back(i^j);
for(i=0;i<N;i++){
if(!vu[i].empty()){
solve(v,w);
for(auto j:vu[i]){
u[j]++;
for(k=0;k<M;k++)ans+=h[k][!((1<<k)&(i^j))];
}
}
if(!vv[i].empty()){
solve(u,w);
for(auto j:vv[i]){
v[j]++;
for(k=0;k<M;k++)ans+=h[k][!((1<<k)&(i^j))];
}
}
if(!vw[i].empty()){
solve(u,v);
for(auto j:vw[i]){
w[j]++;
for(k=0;k<M;k++)ans+=h[k][!((1<<k)&(i^j))];
}
}
}
printf("Case #%d: %llu\n",++Cas,ans);
}
return 0;
}
J How Much Memory Your Code Is Using?
题目描述
求一些变量占用的内存。
解题思路
签到题
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef long long ll;
using namespace std;
map<string,int>mp;
int main(){
int i,t,Cas=0;
mp["char"]=mp["bool"]=1;
mp["int"]=mp["float"]=4;
mp["double"]=mp["longlong"]=8;
mp["__int128"]=mp["longdouble"]=16;
scanf("%d",&t);
while(t--){
ll ans=0,now;
int n;
scanf("%d",&n);
string x,y;
for(i=0;i<n;i++){
cin>>x;
if(x=="long"){
cin>>y;
x=x+y;
}
now=mp[x];
cin>>x;
int flag=0,num=0;//kuohao
for(auto j:x){
if(j=='[')flag=1;
else if(j==']')flag=0;
else if(flag)num=num*10+j-'0';
}
if(!num)num=1;//meiyoukuohao
ans+=num*now;
}
printf("Case #%d: %d\n",++Cas,(ans+1023)/1024);
}
return 0;
}
K Let the Flames Begin
题目描述
求约瑟夫环第$m$轮退出游戏的人，其中总人数为$n$，每轮报数到$k$的人退出游戏。
$1\leq n,m,k\leq 10^{18}$，$min(m,k)<2\times 10^6$。
解题思路
考虑后一半数据范围，当$k$较大的时候，$m$较小，直接逆推即可；当$m$较大的时候，$k$较小，考虑到$n$较大，于是每轮模拟可以删除多个人（一圈以内求多次），逆推即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using namespace std;
typedef long long ll;
const int maxn= 2e6+23;
ll f[maxn];
ll n,m,k;
int T;
int main()
{
cin >> T;int cas=0;
while(T--){
scanf("%lld%lld%lld",&n,&m,&k);
printf("Case #%d: ",++cas);
f[0]=(k-1)%(n-m+1);
if(m<=k){
for(int i=1;i<m;i++) f[i]=(f[i-1]+k)%(n-m+i+1);
printf("%lld\n",f[m-1]+1);
}
else{
if(k==1) {printf("%lld\n",m);continue;}
for(int i=1;i<k;i++) f[i]=(f[i-1]+k)%(n-m+i+1);
ll now=k-1,step=0,v=f[k-1];
while(now+step<m){
if(step!=0) now+=step,v=(v+step*k)%(now+n-m+1);
step=(now+n-m+1-v-1)/(k-1)+1;
}
v=(m-now-1)*k+v;
printf("%lld\n",v%n+1);
}
}
}
L Machining Disc Rotors
题目描述
给一个圆心在原点上的初始圆，有$n$个圆形锯，在这些锯范围内的初始圆的部分会被切除。问最后的圆中，距离最远的两点之间距离是多少。
解题思路
最后的距离必然为一对圆交点或直径，枚举即可。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
using namespace std;
const double eps = 1e-9;
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y) {}
bool operator < (const point &b)
{
return x<b.x||(x==b.x&&y<b.y);
}
};
typedef Point Vector;
Point operator + (Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
Point operator - (Point A,Point B) {return point(A.x-B.x,A.y-B.y);}
point operator * (point A,double B) {return point(A.x*B,A.y*B);}
point operator / (point A,double B) {return point(A.x/B,A.y/B);}
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
return x<0 ? -1 : 1;
}
bool operator == (const point &a,const point &b)
{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
double length(Vector a)
{
return sqrt(dot(a,a));
}
double angle(v a,v b)
{
return acos(dot(a,b))/length(a)/length(b);
}
double cross(v a,v b)
{
return a.x*b.y-a.y*b.x;
}
struct Circle
{
Point c;double r;
//Circle(Point c,double r) :c(c),r(r){}
Point pnt(double a)
{
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
double Angle(Vector v)
{
return atan2(v.y,v.x);
}
int getCircleCircleIntersection(Circle c1,Circle c2,vector<Point> &sol)
{
double d=length(c1.c-c2.c);
if(dcmp(d)==0) return 0;
if(dcmp(c1.r+c2.r-d)<0) return 0;
if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0;
double a=Angle(c2.c-c1.c);
double da=acos(( c1.r*c1.r + d*d - c2.r*c2.r )/( 2*c1.r * d ));
Point p1 =c1.pnt(a-da),p2=c1.pnt(a+da);
sol.push_back(p1);
if(p1==p2) return 1;
sol.push_back(p2);
return 2;
}
const int maxn = 123;
int T,n;
Circle a[maxn],c;
vector<point> pt;
inline double dis(int i,int j)
{
return sqrt((pt[i].x-pt[j].x)*(pt[i].x-pt[j].x)+(pt[i].y-pt[j].y)*(pt[i].y-pt[j].y));
}
bool check(Point k)
{
Point p=Point(0,0)-k;
for(int i=0;i<n;i++){
if(dot(p-a[i].c,p-a[i].c)<a[i].r*a[i].r) return true;
}
return false;
}
int main()
{
cin >> T;int cas=1;
while(T--){
scanf("%d%lf",&n,&c.r);
c.c.x=c.c.y=0;
pt.resize(0);
for(int i=0;i<n;i++) scanf("%lf%lf%lf",&a[i].c.x,&a[i].c.y,&a[i].r),getCircleCircleIntersection(c,a[i],pt);
printf("Case #%d: ",cas++);
double ans=0;
for(int i=0;i<pt.size();i++){
if(!check(pt[i])){
printf("%.10f\n",2*c.r);
goto A;
}
}
for(int i=0;i<pt.size();i++){
for(int j=i+1;j<pt.size();j++){
ans=max(ans,dis(i,j));
}
}
printf("%.10f\n",ans);
A:;
}
}
M Renaissance Past in Nancy
题目描述
有$n$种物品，第$i$种物品有$a_i$种，其价格为$b_i$。有$q$次询问，每次询问一个区间$[l,r]$，问总花费钱数最多为$c$，在$[l,r]$种物品之内买物品的方案数。
解题思路
将每一种物品用生成函数表示为$1+x^b+x^{2b}+…+x^{ab}$
$=\frac{x^{(a+1)b}-1}{x^b-1}=(1-x^{(a+1)b})(1+x^b+…+x^{kb}+…)$
于是$[l,r]$方案数即为$\prod_{i=l}^{r}(1+x^{b_i}+…+x^{a_ib_i})$中指数在$c$以下的系数之和。
考虑做一个前缀积，但要做前缀积需要类似重载减法运算符。对应在这个生成函数上，求$\prod_{i=l}^{r}=\prod_{i=1}^{r}\frac{x^{(a+1)b}-1}{x^b-1}\prod_{i=1}^{l-1}\frac{x^b-1}{x^{(a+1)b}-1}$，故可以维护两种背包，分别对分子分母做完全背包和$01$背包。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef long long ll;
using namespace std;
const int mod=1000000007;
int f[M],g[M],sf[N][M],sg[N][M];
void add01(int *f,int v){
int i;
for(i=M-1;i>=v;i--)f[i]=(f[i]-f[i-v]+mod)%mod;
}
void addcomplete(int *f,int v){
int i;
for(i=v;i+v<M;i++)f[i]=(f[i]+f[i-v])%mod;
}
int main(){
int i,j,T,Cas=0,n,m;
scanf("%d",&T);
while(T--){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
f[0]=g[0]=sg[0][0]=sf[0][0]=1;
for(j=1;j<M;j++)sf[0][j]=1,sg[0][j]=0;
for(i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
add01(f,b*(a+1));
add01(g,b);
addcomplete(f,b);
addcomplete(g,b*(a+1));
sf[i][0]=f[0];sg[i][0]=g[0];
for(j=1;j<M;j++){
sf[i][j]=(sf[i][j-1]+f[j])%mod;
sg[i][j]=g[j];
}
}
int lastans=0;
printf("Case #%d:\n",++Cas);
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
l=(l+lastans)%n+1;
r=(r+lastans)%n+1;
if(l>r)swap(l,r);
ll ans=0;
for(i=0;i<=c;i++)ans=(ans+1LL*sf[r][i]*sg[l-1][c-i])%mod;
printf("%lld\n",ans);
lastans=ans;
}
}
return 0;
}