D. Meta-set
题意：给定一段长为k的数字组合，每个数组的选取为{0,1,2}。找到三个组合满足每位上的k都相同或者都不相同可称为1队，对于5个组合组成的meta-set，要求其中对数要大于等于2.
思路：
1.可发现每两个组合可确定一个唯一的组合，围绕着这个组合可产生多对meta-set。
2.进一步发现以自己为中心的组合meta-set的个数为x*(x-1)/2.
3.接着就是代码的处理。我是将每个组合变成字符串存了起来，用vector也可以。
思维误区：
开始认为组合的中心是已知的，采用O(n2 )循环,从每个组合开始记录有多少满足条件的对数，
再取C(n,2)累加结果。这是错误的，因为这个组合不作为中心时，可作为边缘加入到其他中心的组合中。
#include <bits/stdc++.h>
#define int long long
#define ios cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
#define endl '\n'
#define eps 1e-7
using namespace std;
int n,k,s[1005][25];
map<string,int>mp,mm;
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
string ss="";
for(int j=1;j<=k;j++)
{
cin>>s[i][j];ss+='0'+s[i][j];
}
mp[ss]=i;
}
int ans=0;
for(int i=1;i<=n;i++)
{
int tmp=0;
for(int j=i+1;j<=n;j++)
{
string ss="";
for(int g=1;g<=k;g++)
{
if(s[i][g]==s[j][g]) ss+='0'+s[i][g];
else ss+='0'+(3-s[i][g]-s[j][g]);
}
mm[ss]++;
/*
if(mp[ss]&&mp[ss]>j)
{
for(int g=1;g<=k;g++) cout<<s[i][g]<<" ";
cout<<"gg";
for(int g=1;g<=k;g++) cout<<s[j][g]<<" ";
cout<<"kkk "<<ss<<endl;
tmp++;
}
*/
}
}
for(int i=1;i<=n;i++)
{
string ss="";
for(int j=1;j<=k;j++) ss+='0'+s[i][j];
ans+=(mm[ss]-1)*mm[ss]/2;
}
cout<<ans<<endl;
}
signed main()
{
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
C. Digital Path
去掉注释可跟踪代码的执行。
思路：
1.正常考虑一个点，他可能不是终点，也不是起点，若从它开始向两端深搜，不太可能。
2.换个想法，从终点开始搜索，周围没有比他大的数，开始深搜。
记忆化方程dp[x][y][len]含义:到达x行y列路径长度为len的方案数。若长度>=4,则都记录为4
转移方程:dp[x][y][len]+=dp[nx][ny][len-1],搜索数字比他小1的方格，可由它转移而来
dp[x][y][4]+=dp[nx][ny][4]，到达相邻格子的也并非为正好为4
3.若len=1，并且可作为一条路径的起点，则dp[x][y][1]=1,否则为0.
#include <bits/stdc++.h>
#define int long long
#define ios cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
#define endl '\n'
#define eps 1e-7
using namespace std;
const int mod=1e9+7;
int n,m,a[1005][1005],dp[1005][1005][5];
bool vis[1005][1005];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,-1,1};
//判终点
int ch1(int x,int y)
{
for(int i=1;i<=4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[x][y]==a[nx][ny]-1) return 0;
}
return 1;
}
//判起点
int ch2(int x,int y)
{
for(int i=1;i<=4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[x][y]==a[nx][ny]+1) return 0;
}
return 1;
}
int dfs(int x,int y,int len)
{
if(len==1)
{
if(ch2(x,y)) dp[x][y][len]=1; else dp[x][y][len]=0;
//cout<<x<<" "<<y<<" "<<len<<" "<<dp[x][y][len]<<endl;
return dp[x][y][len];
}
if(dp[x][y][len]!=-1) return dp[x][y][len];
int tmp=0;
for(int i=1;i<=4;i++)
{
int nx=dx[i]+x,ny=dy[i]+y;
if(nx<1||nx>n||ny<1||ny>m||a[x][y]!=a[nx][ny]+1) continue;
tmp=(tmp+dfs(nx,ny,len-1))%mod;
if(len==4)
{
//cout<<nx<<" "<<ny<<endl;
tmp=(tmp+dfs(nx,ny,len))%mod;
}
}
dp[x][y][len]=tmp%mod;
//cout<<x<<" "<<y<<" "<<len<<" "<<dp[x][y][len]<<endl;
return dp[x][y][len];
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++) for(int k=0;k<5;k++) dp[i][j][k]=-1;
int ans=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
if(a[i][j]!=-1&&ch1(i,j))
{
//cout<<"gg"<<endl;
ans=(ans+dfs(i,j,4))%mod;
}
}
cout<<ans<<endl;
}
signed main()
{
ios;
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
K. Triangle
看了2个多小时，之前没怎么做过计算几何的题目，本题思路不难，但代码的实现挺难的。这次算积累了一套计算几何的板子，可算距离、点积、叉积、记录直线，判断点在线上(两个条件)
采用向量的方式，不需要考虑斜率不存在的情况。
#include <bits/stdc++.h>
#define int long long
#define ios cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
const int mod=1e9+7;
const double eps=1e-8;
double x[5],y[5];
struct Point
{
double x,y;
Point(){};
Point(double xx,double yy){x=xx,y=yy;}
Point operator -(Point B)
{
return Point(x-B.x,y-B.y);
}
}p[5],pos[5];
struct Line
{
Point p1,p2;
Line(){};
Line(Point p11,Point p22){p1=p11,p2=p22;}
}lin[5];
int sgn(double x)
{
if(abs(x)<eps) return 0;
return x<0?-1:1;
}
double dis(Point p1,Point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double cross(Point p1,Point p2)
{
return p1.x*p2.y-p1.y*p2.x;
}
double dot(Point p1,Point p2)
{
return p1.x*p2.x+p1.y*p2.y;
}
int Pt_on_Line(Point p,Line ln)
{
return sgn(cross(p-ln.p1,ln.p1-ln.p2))==0&&sgn(dot(p-ln.p1,p-ln.p2))<=0;
}
void solve()
{
for(int i=1;i<=4;i++) cin>>p[i].x>>p[i].y;
lin[1]=Line(p[1],p[2]);lin[2]=Line(p[1],p[3]);lin[3]=Line(p[2],p[3]);
if(Pt_on_Line(p[4],lin[1])==0&&Pt_on_Line(p[4],lin[2])==0&&Pt_on_Line(p[4],lin[3])==0)
{
cout<<-1<<endl;return;
}
int g=0;
for(int i=1;i<=3;i++)
{
if(Pt_on_Line(p[4],lin[i])==1) {g=i;break;}
}
if(g==1) pos[1]=p[3];else if(g==2) pos[1]=p[2];else pos[1]=p[3];
if(dis(p[4],lin[g].p1)>=dis(p[4],lin[g].p2))
pos[2]=lin[g].p1,pos[3]=lin[g].p2;
else
pos[2]=lin[g].p2,pos[3]=lin[g].p1;
double tmp=(dis(pos[2],pos[3])/dis(pos[2],p[4]))*0.5;
double dx=pos[2].x+tmp*(pos[1].x-pos[2].x);
double dy=pos[2].y+tmp*(pos[1].y-pos[2].y);
cout<<fixed<<setprecision(12)<<dx<<" "<<dy<<endl;
}
signed main()
{
ios;
int T;cin>>T;
while(T--)
solve();
return 0;
}
