由于很菜，只过了BCDF4题，其中C是队友切的，赛后又过了J，所以写一下BDFJ四道题题解。
B
这道题卡了不少人，我也被卡了一会（罚时3次），其实不算难。
首先可以O(n^2)统计出所有可能的圆心（显然最优解一定至少满足原点和任意另外两点构成的圆，除非只能经过1点）。然后判断每个点出现的次数即可。
然而这道题恶心的地方是一共2e6个点，如果用map统计次数会卡常超时（map的常数太大了）。解决方法是直接排序之后计数即可。
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-10
struct Point{
double x,y;
Point(double x,double y){
this->x=x;
this->y=y;
}
Point(){
x=y=0;
}
};
Point p[5000];
//过三点求圆心坐标
Point waixin(Point a,Point b,Point c)
{
double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1*a1 + b1*b1)/2;
double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2*a2 + b2*b2)/2;
double d = a1*b2 - a2*b1;
return Point(a.x + (c1*b2 - c2*b1)/d, a.y + (a1*c2 -a2*c1)/d);
}
pair<double,double> m[2222222];
int main(){
int n,i,j=0,k=0;
cin>>n;
for(i=0;i<n;i++){
cin>>p[i].x>>p[i].y;
}
Point z(0,0);
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(fabs(p[i].x*p[j].y-p[i].y*p[j].x)>eps){
Point temp=waixin(p[i],p[j],z);
// cout<<p[i].x<<" "<<p[i].y<<" "<<p[j].x<<" "<<p[j].y<<" "<<temp.x<<" "<<temp.y<<endl;
m[k++]=make_pair(temp.x,temp.y);
}
}
}
if(k==0){cout<<1;return 0;}
sort(m,m+k);
int cnt=1,ma=1;
for(i=0;i<k-1;i++){
if(fabs(m[i].first-m[i+1].first)<eps&&fabs(m[i].second-m[i+1].second)<eps)cnt++,ma=max(ma,cnt);
else cnt=1;
}
for(i=1;i<=n;i++)if(i*(i-1)==2*ma)break;
cout<<i;
}D
签到题。只用算出两个时间对应秒数，然后abs就行了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a1,a2,a3,b1,b2,b3;
scanf("%d:%d:%d",&a1,&a2,&a3);
scanf("%d:%d:%d",&b1,&b2,&b3);
int t1=a1*3600+a2*60+a3;
int t2=b1*3600+b2*60+b3;
cout<<abs(t1-t2);
}F
首先用gcd把矩阵全部算出来，然后用两次单调队列就能算出每个小正方形的最大值了。
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-10
int a[5005][5005];
int dp[5005][5005];
struct node{
int id;
int val;
}tmp;
int gcd(int x,int y){
return x%y==0?y:gcd(y,x%y);
}
int lcm(int x,int y){
return x*y/gcd(x,y);
}
int main(){
int i,n,m,j,k;
cin>>n>>m>>k;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
a[i][j]=lcm(i,j);
}
}
for(i=1;i<=n;i++){
deque<node>maxn;
for(j=1;j<=m;j++){
if(!maxn.empty() && j-maxn.front().id>=k) maxn.pop_front();
while(!maxn.empty() && maxn.back().val<a[i][j]) maxn.pop_back();
tmp.val=a[i][j];
tmp.id=j;
maxn.push_back(tmp);
if(j>=k)
{
dp[i][j]=maxn.front().val;
}
}
}
long long sum=0;
for(j=k;j<=m;j++){
deque<node>maxn;
for(i=1;i<=n;i++){
if(!maxn.empty() && i-maxn.front().id>=k) maxn.pop_front();
while(!maxn.empty() && maxn.back().val<dp[i][j]) maxn.pop_back();
tmp.val=dp[i][j];
tmp.id=i;
maxn.push_back(tmp);
if(i>=k)
{
sum+=maxn.front().val;
}
}
}
cout<<sum<<endl;
}J
这道题赛中没过，赛后过的。
最开始的思路是：现在知道了k次以后的情况，对于每个大小为p的cycle而言，变换p次之后又会回到初始状态。因此计算所有cycle大小的lcm，求k对这个lcm的逆元就可以了。
然而这个方案并不可行，因为这个lcm有可能是个天文数字，逆元基本没办法去求。
赛后想到的解决方案是：由于每个cycle是独立的，因此也可以独立的计算每个cycle每次转换的情况，这样单独求k关于每个p的逆元之后单独解决就行了。
ps：cycle指每个数变换成自己经历的所有数的一个循环。例如；2 3 1 5 4而言，有1->2->3和4->5这两个cycle。
为什么求逆元就能解决？因为大小为p的cycle，变换p次一定能得到它本身。现在已知变换k次的情况，求变换1次的情况，那么只要求出k在模p意义下的逆元x。变换x次【变换k次】，最终和变换1次就是等价的了。
关于最终的变换x次的求法，我用的是倍增来解决的。求出初始排列的1次变换、2次变换、4次变换、8次变换的结果，这样根据二进制就能表达出所有变换的情况。
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-10
#define ll long long
int mod;
int a[111111],visited[111111];
int dp[111111][20],out[111111][2];
int main(){
ll i,n,m,j,k;
cin>>n>>k;
for(i=1;i<=n;i++){
cin>>a[i];
dp[i][0]=a[i];
out[i][0]=i;
}
ll tt=i;
//cout<<tt<<endl;
for(j=1;j<20;j++){
for(i=1;i<=n;i++){
dp[i][j]=dp[dp[i][j-1]][j-1];
// cout<<dp[i][j]<<" ";
}
// cout<<endl;
}
for(i=1;i<=n;i++){
vector<int>v;
j=i;
if(visited[i])continue;
while(!visited[j]){
v.push_back(j);
visited[j]=1;
j=a[j];
}
int temp=k%v.size();
for(j=1;j<v.size();j++)if(temp*j%v.size()==1)break;
for(int kk=0;kk<20;kk++){
if(j&1){
for(int h=0;h<v.size();h++)out[v[h]][1]=out[dp[v[h]][kk]][0];
for(int h=0;h<v.size();h++)out[v[h]][0]=out[v[h]][1];
}
j/=2;
}
}
for(i=1;i<=n;i++)cout<<out[i][0]<<" ";
}
京公网安备 11010502036488号