題目背景

使用過Android 手機的同學一定對手勢解鎖屏幕不陌生。Android 的解鎖屏幕由3X3 個點組成，手指在屏幕上畫一條線，將其中一些點連接起來，即可構成一個解鎖圖案。如下面三個例子所示:

??

題目描述

畫線時還需要遵循一些規則:

連接的點數不能少于4 個。也就是說只連接兩個點或者三個點會提示錯誤。

兩個點之間的連線不能彎曲。

每個點只能“使用”一次，不可重復。這里的“使用”是指手指劃過一個點，該點變綠。

兩個點之間的連線不能“跨過”另一個點，除非那個點之前已經被“使用”過了。

對于最后一條規則，參見下圖的解釋。左邊兩幅圖違反了該規則; 而右邊兩幅圖(分別為2->4-1-3-6 和6->5-4->1->9-2) 則沒有違反規則，因為在“跨過”點時，點已經被“使用”過了。

現在工程師希望改進解鎖屏幕，增減點的數目，并移動點的位置，不再是一個九宮格形狀，但保持上述畫線的規則不變。請計算新的解鎖屏幕上，一共有多少滿足規則的畫線方案。

輸入輸出格式

輸入格式：

?

輸入文件第一行，為一個整數n,表示點的數目。

接下來n 行，每行兩個空格分開的整數?x_ixi??和?y_iyi??,表示每個點的坐標。

?

輸出格式：

?

輸出文件共一行，為題目所求方案數除以100000007 的余數。

?

輸入輸出樣例

輸入樣例#1：?
4 0 0 1 1 2 2 3 3 輸出樣例#1：?
8 輸入樣例#2：?
4 0 0 0 1 0 2 1 0 輸出樣例#2：?
18

說明

樣例#1解釋: 設4 個點編號為1到4,方案有1->2->3->4，2->1->3->4，3->2->1->4，2->3->1->4，及其鏡像4->3->2->1,3->4->2->1,2->3->4->1，3->2->4->1。

對于30%的數據，?1≤n≤101≤n≤10

對于100%的數據，?-1000≤x_i,y_i≤1000,1≤n<20?1000≤xi?,yi?≤1000,1≤n<20?。各點坐標不相同

?

?

? ? 不是很難想的狀壓，f[S][i]表示已經走了集合S中的點，且目前在點i 的方案數，直接轉移就行了。

?

#include<bits/stdc++.h> #define ll long long using namespace std; const int ha=100000007; const int maxn=1100005; inline int add(int &x,int y){ x+=y; if(x>=ha) x-=ha;} int ci[35],n,m,px[35],py[35],BC[maxn]; int S[35][35],f[maxn][23],ans;inline void init(){ci[0]=1;for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;for(int i=1;i<ci[20];i++) BC[i]=BC[i^(i&-i)]+1; }inline void prework(){for(int i=0;i<n;i++)for(int j=0;j<n;j++){S[i][j]=ci[i]|ci[j];for(int k=0;k<n;k++){if(px[k]>max(px[i],px[j])||px[k]<min(px[i],px[j])) continue;if(py[k]>max(py[i],py[j])||py[k]<min(py[i],py[j])) continue;if((px[i]-px[j])*(py[i]-py[k])==(px[i]-px[k])*(py[i]-py[j])) S[i][j]|=ci[k];}} }inline void dp(){for(int i=0;i<n;i++) f[ci[i]][i]=1;for(int i=1;i<=n;i++)for(int j=0;j<ci[n];j++) if(BC[j]==i)for(int k=0;k<n;k++) if(f[j][k]){if(i>=4) add(ans,f[j][k]);for(int l=0;l<n;l++) if(!(ci[l]&j)&&BC[(j&S[k][l])^S[k][l]]==1) add(f[j|ci[l]][l],f[j][k]);} }int main(){init(),scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d%d",px+i,py+i);prework(),dp();printf("%d\n",ans);return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/8905916.html

總結

以上是生活随笔為你收集整理的[CQOI2018] 解锁屏幕的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。