当前位置 : 主页 > 编程语言 > java >

基本计数方法专题

来源：互联网 收集：自由互联 发布时间：2022-10-26
​​例题​​ ​​UVA 11401 Triangle Counting​​ ​​UVA 11806 Cheerleaders​​ ​​LA 3516 Exploring Pyramids​​ ​​UVA 11361 Investigating Div-Sum Property​​ ​​LA 4123 Glenbow Museum​​ ​​UVA 10253 Ser


  • ​​例题​​
  • ​​UVA 11401 Triangle Counting​​
  • ​​UVA 11806 Cheerleaders​​
  • ​​LA 3516 Exploring Pyramids​​
  • ​​UVA 11361 Investigating Div-Sum Property​​
  • ​​LA 4123 Glenbow Museum​​
  • ​​UVA 10253 Series-Parallel Networks​​
  • ​​习题​​
  • ​​UVA 11038 How many 0s​​
  • ​​UVA 10883 Supermean​​
  • ​​UVA 1510 Neon Sign​​
  • ​​UVA 1393 Highway CERC 2006​​
  • ​​UVA 10237 Bishops​​
  • ​​13补充​​
  • ​​极角排序流​​
  • ​​UVA 11529 Strange Tax Calculation​​
  • ​​LA 4064 Magenetic Train Tracks Dhaka 2007​​
  • ​​LA 5092 Permutation Counting Harbin 2010​​
  • ​​UVA 11139 Counting Quadrilaterals​​
  • ​​UVA 1425 Metal​​
  • ​​HDU 3723 Delta Wave Tianjin 2010​​
  • ​​25补题​​
  • ​​LA 3357UVA 1350 Pinary Seoul 2005​​
  • ​​UVA 12075 Counting Triangles​​


例题

UVA 11401 Triangle Counting

题意:在1..n中取三个不同的整数，使其恰能构成3角形三边长，求取法数

枚举最大的边x,假设其中一条边为y，另一条边的取值范围是(x−y,x),共y-1个解，总数为(x−1)(x−2)/2
去掉y=z的三角形x−1−x/2个，除2排除y<z的

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll f[1000000+10];

int main()
{
// freopen("uva11401.in","r",stdin);
// freopen(".out","w",stdout);

MEM(f)
Fork(i,4,1000000)
f[i] = f[i-1] + ((ll)(i-1)*(i-2)/2-(ll)(i-1)/2)/2;
int n;
while(cin>>n) {
if (n<3) break;
cout<<f[n]<<endl;
}

return 0;
}

UVA 11806 Cheerleaders

题意：在一个n*m的矩形网格里放k个石子（每个格子最多放一个），使得最外边的每1行/列都至少有一个石子，有多少放法？
容斥

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll C[510][510]={0};
int main()
{
// freopen("uva11806.in","r",stdin);
// freopen(".out","w",stdout);
C[0][0]=1;
For(i,505) {
C[i][0]=1;
For(j,i) C[i][j] =add( C[i-1][j],C[i-1][j-1]);
}
int T=read();
For(kcase,T) {
ll ans=0;
int m=read(),n=read();
int k=read();
Rep(S,16) {
int b=0;
int r=m,c=n;
if (S&1) {r--; b^=1;}
if (S&2) {r--; b^=1;}
if (S&4) {c--; b^=1;}
if (S&8) {c--; b^=1;}
if (!b) ans=add(ans,C[r*c][k]);
else ans=sub(ans,C[r*c][k]);
ans%=F;
}
Pr(kcase,ans)
}

return 0;
}

LA 3516 Exploring Pyramids

题意：给一个树的dfs序列，某些节点具有相同的编号，问有多少棵树能与之队应(假设树为多叉树，每个节点的任意2子节点左右之分,dfs序优先向左走）

区间dp

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
char s[MAXN];
int n;
ll dp[MAXN][MAXN];
ll f(ll a,ll b){
if (a==b) return 1;
if (s[a]!=s[b]) return 0;
if (dp[a][b]!=-1) return dp[a][b];

dp[a][b] = 0;
Fork(k,a+2,b) {
upd(dp[a][b] , mul(f(a+1,k-1) , f(k,b)));
}
return dp[a][b];
}
int main()
{
// freopen("la3516.in","r",stdin);
// freopen(".out","w",stdout);
while (cin>>s) {
memset(dp,-1,sizeof(dp));
int n=strlen(s);
cout<<f(0,n-1)<<endl;

}


return 0;
}

UVA 11361 Investigating Div-Sum Property

题意：已知正整数a,b,k,求有多少整数n满足a≤n≤b,k|n,k|(n的数位和)
1≤a,b≤232,1≤k<10000

数位dp，注意 k≥100的时候答案必为0

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (k)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case %d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[i]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;

ll a,b;
ll k;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
//ll sub(ll a,ll b){if (a>=b) return (a-b)%F; else return (((b-a)%F) ==0 )? 0 : F-1-(b-a)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll t10[15];
ll dp[15][105][105];
ll f(int d,ll m1,ll m2) {
// cout<<d<<m1<<m2<<endl;
if (!d) {
if (m1==0 && m2==0) return 1;
return 0;
}
if (dp[d][m1][m2]!=-1) {
return dp[d][m1][m2];
}

ll ans=0;
Rep(x,10) {
ans+= f(d-1,sub(m1,x),sub(m2,mul(x,t10[d-1])));
}
dp[d][m1][m2]=ans;
return ans;
}
int len;
char s[100];
ll dfs(int i,ll m1,ll m2) {
if (i==len) {
return f(0,m1,m2);
}
ll ans=0;
Rep(j,s[i]-'0') {
ans+=f(len-i-1,sub(m1,j),sub(m2,mul(t10[len-i-1],j)) );
}
ans+=dfs(i+1,sub(m1,s[i]-'0'),sub(m2,t10[len-i-1]*(s[i]-'0')%F ) );
return ans;
}
void to_s(ll a) {
stringstream ss;
ss<<a;
ss>>s;
len=strlen(s);
return;
}
int main()
{
// freopen("uva11361.in","r",stdin);
// freopen(".out","w",stdout);
t10[0]=1;
For(i,14) {
t10[i]=t10[i-1]*10;
}
int T=read();
while(T--) {
memset(dp,-1,sizeof(dp));
cin>>a>>b>>k;
if (k>=100) {
puts("0"); continue;
}
to_s(b);
ll ans=0;
ans+=dfs(0,0,0);
to_s(a-1);
ans-=dfs(0,0,0);
cout<<ans<<endl;
}

return 0;
}

LA 4123 Glenbow Museum

题意：对于一个边平行于坐标轴的多边形，我们可以用一个由R和O组成的序列来描述它：从某个顶点开始按照逆时针顺序走，碰到一个90°的内角记R；碰到一个270°的内角记O。这样的序列称为角度序列。定义星型多边形为多边形中存在一个点可以看到多边形边界上每一个点。现在给定正整数n，求有多少个长度为L的角度序列至少可以对应一个星型多边形。其中多边形的每条边长任意。

本题等价于：长度为L的序列，要求序列中只有O和R，且R比O多4个，且头尾不能同位O，且不能有连续2个O出现，问符合条件的序列数

考虑R有4个,OR有p-4个，其排成的不同序列的个数为C4p
再考虑R…O的序列数，刚好是O…R的序列数C4p−1
注意奇数和n<4时答案为0

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define

int main()
{
// freopen("la4123.in","r",stdin);
// freopen(".out","w",stdout);
int n;
int kcase=0;
while (cin>>n &&n){
ll ans=0;
if (n<4||n%2==1) {
Pr(++kcase,0) continue;
}
ll p=(n-4)/2+4;

ans = p*(p-1)*(p-2)*(p-3)/4/3/2;
if (p>4) ans+=(p-1)*(p-2)*(p-3)*(p-4)/4/3/2;
Pr(++kcase,ans)
}


return 0;
}

UVA 10253 Series-Parallel Networks

题意：有一个n条边的串并联网络，
2个串并联网络，串的顺序调换，并的顺序调换，视为相同
问满足题意的网络有几个？
1≤n≤30

考虑树dp，
假设这个串并联网络最后一次是串还是并，考虑所有边数划分方案

注意：必须划分成至少2部分(不然不算串并)

可重复选择元素的组合数
设第i个元素选xi个，答案为x1+x2+…+xn=k的非负元素的解的个数，积y1+y2+…+yn=n+k的正整数解个数，隔板法即可

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll C(ll n,ll m) {
double ans=1;
Rep(i,m) ans*=n-i;
For(i,m) ans/=i;
return (ll)(ans+0.5);
}
#define
ll f[MAXN],d[MAXN][MAXN];
ll calc(int i,int j) { // 子树的叶子最多i个， j个叶子
if (d[i][j]!=-1) return d[i][j];
d[i][j]=0;
for(int p=0;j-p*i>=0;p++) {
d[i][j] += C(f[i]+p-1,p)*calc(i-1,j-i*p);
}
return d[i][j];
}
int main()
{
// freopen("uva10253.in","r",stdin);
// freopen(".out","w",stdout);
memset(d,-1,sizeof(d));
d[0][0]=1;
For(i,30) d[i][0]=1,d[0][i]=0;

f[1]=1;
For(i,29) {
f[i+1] = calc(i,i+1);
}
int n;
while(cin>>n &&n) {
if (n==1) puts("1");
else cout<<2*f[n]<<endl;
}

return 0;
}

习题

UVA 11038 How many 0’s?

题意：求m~n的所有整数中0出现的次数

不要数位dp，
考虑第i位为0的数在0~n中出现的次数

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll calc(ll n){
if (n<0) return 0;
ll ans=1; //把0算上
ll Left=n,Right=0,j=1;
while(Left) {
int p=Left%10; Left/=10;
if (p) ans += Left*j;
else ans += (Left-1)*j + Right+1;

Right += j*p;
j*=10;
}
return ans;
}
int main()
{
// freopen("uva11038.in","r",stdin);
// freopen(".out","w",stdout);

ll m,n;
while (cin>>m>>n && (m>=0) && (n>=0)) {
cout<<calc(n)-calc(m-1)<<endl;

}


return 0;
}

UVA 10883 Supermean

题意：给n个数，每相邻两个数求平均数得到n-1个数，重复操作得到n-2个数……，最后得到1个数，求这个数。

二项式系数
乘法取log

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n;
void work() {
double p=0;

double p2=-(double)(n-1)*log(2);
double ans=0;

double c;
Rep(i,n) {
scanf("%lf",&c);
ans += exp(p+p2)*c;
p+=log((double)n-i-1)-log((double)i+1);
}
printf("%.3lf\n",ans);
}
int main()
{
// freopen("uva10883.in","r",stdin);
// freopen(".out","w",stdout);

int T=read();
For(kcase,T) {
printf("Case #%d: ",kcase);
n=read();
work();
}

return 0;
}

UVA 1510 Neon Sign

题意：n个点两两连边，已知没条边的颜色（只有2种），求单色三角形数。

经典做法

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
ll deg[MAXN];
int main()
{
// freopen("uva1510.in","r",stdin);
// freopen(".out","w",stdout);

int T=read();
while(T--) {
int n=read();
MEM(deg)
For(i,n-1)
Fork(j,i+1,n) {
int p=read();
if (p) deg[i]++,deg[j]++;
}
ll ans=0;
For(i,n) ans += deg[i]*(n-1-deg[i]);
cout<< (ll)n*(n-1)*(n-2)/6 -ans/2<< endl;
}


return 0;
}

UVA 1393 Highway, CERC 2006

题意：n行m列的点阵，有多少条非水平非竖直的直线穿过点阵中至少2个点？
令f[i][j]表示 (0,0)−>(n,m) 经过的直线是否符合条件，但是2倍的地方要减回去
然后求2次二维前缀和就是答案。

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int gcd(int a,int b){if (!b) return a;return gcd(b,a%b);}
ll f[350][350];
int main()
{
// freopen("uva1393.in","r",stdin);
// freopen(".out","w",stdout);

MEM(f)
For(i,300) For(j,300) {
if (gcd(i,j)==1) f[i][j]=1;
else if (gcd(i,j)==2) f[i][j]=-1;
}
For(i,300) For(j,300) {
f[i][j] += f[i][j-1] + f[i-1][j] - f[i-1][j-1];
}
For(i,300) For(j,300) {
f[i][j] += f[i][j-1] + f[i-1][j] - f[i-1][j-1];
}

int n,m;
while(cin>>n>>m && n) cout<<f[n-1][m-1]*2<<endl;


return 0;
}

UVA 10237 Bishops

题意：在n*n的棋盘上放k个互不攻击的象的方案数。两个象不攻击当且仅当它们不处于同一斜线上

把棋盘旋转45度，然后乱搞

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
int n;
ll f[MAXN][MAXN],g[MAXN][MAXN];
void work(int n,int k) {
MEM(f) f[0][0]=1;
For(i,n) f[i][0]=1;
For(i,n)
For(j,k) {
int len=(i+1)/2*2 -1;
f[i][j] = f[i-1][j] + f[i-1][j-1] * (len-j+1);
}

MEM(g) g[0][0]=1;
For(i,n) g[i][0]=1;
For(i,n)
For(j,k) {
int len=(i+1)/2*2 ;
g[i][j] = g[i-1][j] + g[i-1][j-1] * (len-j+1);
}
}
int main()
{
// freopen("uva10237.in","r",stdin);
// freopen(".out","w",stdout);
int n,k;
work(30,30);
while(cin>>n>>k&& n) {

ll ans=0;
Rep(i,k+1) ans += f[n][i] * g[n-1][k-i];
cout<<ans<<endl;
}


return 0;
}

3.13补充

极角排序流

UVA 11529 Strange Tax Calculation

题意：给n个点，无三点共线，随机取3个点构成一个三角形，问其中包含的点的个数的期望。

LA 4064 Magenetic Train Tracks ,Dhaka 2007

题意：给n个点，无三点共线，问构成的直角和锐角三角形的个数。

n≤1200

2题很类似所以放一起，
大致都是枚举一个点，然后以这个点为准对剩下的点极角排序，最后转一圈，用单调队列（或者说双指针）统计

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#define
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
pair<double,double> p[MAXN];
double ang(pair<double,double> p,pair<double,double> p2) {return atan2(p2.se-p.se,p2.fi-p.fi); }

int kcase=0,n;
double r[MAXN];
int main()
{
// freopen("uva11529.in","r",stdin);
// freopen(".out","w",stdout);

while(cin>>n && n)
{
For(i,n) cin>>p[i].fi>>p[i].se;
ll ans=0;
For(i,n) {
int m=0;
For(j,n)
if (j^i)
Rep(k,2) r[++m]=pi*k*2+ang(p[i],p[j]);
sort(r+1,r+m+1);
int mv=1;
For(j,n-1) {
while (r[mv]<r[j]+pi) ++mv;
int cnt=mv-j-1;
ans += (ll) cnt *(cnt-1) / 2;
}


}
Pr(++kcase,((double)n*(n-1)*(n-2)*(n-3)/6-(double)ans)/n/(n-1)/(n-2)*6);
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#define
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
ll gcd(ll a,ll b){if (!b) return a ; return gcd(b,a%b);}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
pair<ll,ll> p[MAXN];
double ang(pair<ll,ll> p,pair<ll,ll> p2) { return atan2((double)p2.se-p.se,(double)p2.fi-p.fi); }

int kcase=0,n;
double r[MAXN];
int main()
{
// freopen("la4064.in","r",stdin);
while(cin>>n && n)
{
For(i,n) cin>>p[i].fi>>p[i].se;
ll ans=0;
For(i,n) {
int m=0;
For(j,n)
if (j^i)
Rep(k,2) r[++m]=pi*k*2+ang(p[i],p[j]);
sort(r+1,r+m+1);
int mv=1,mv2=1;
For(j,n-1) {
while (r[mv]<=r[j]+pi/2-eps) ++mv;
while (r[mv2]<r[j]+pi) ++mv2;
int cnt=mv2-mv;
ans += cnt;
}
}
Pr(++kcase,((ll)(n-1)*(n-2)*n/6-ans));
}
// {
// freopen("la4064_makedata.in","w",stdout);
// cout<<"100"<<endl;
// For(i,100) {
// int a=rand()%10000,b=rand()%10000;
// if (gcd(a,b)==1) cout<<a<<' '<<b<<endl; else i--;
// }
// cout<<"0\n";
//
// }
return 0;
}

LA 5092 Permutation Counting, Harbin 2010

题意：1~n的排列(a1,…,an)，恰有k个位置ai>i,已知n，求方案数
n≤1000
dp题，首先很容易想出递推式
f(n,k)=(k+1)∗f(n−1,k)+(n−k)∗f(n−1,k−1)
打表发现

n \ m 0 1 2 3 4 5 6 7 8
1 1
2 1 1
3 1 4 1
4 1 11 11 1
5 1 26 66 26 1
6 1 57 302 302 57 1
7 1 120 1191 2416 1191 120 1
8 1 247 4293 15619 15619 4293 247 1
9 1 502 14608 88234 156190 88234 14608 502 1

就是欧拉数，​​wiki链接​​

不过讲道理打表都能直接过了DAZE

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
Rep(j,m) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
ll f[MAXN][MAXN]={0};
int main()
{
// freopen("uva1485.in","r",stdin);
For(i,1000)
{
f[i][0]=1;
For(j,i) {
f[i][j]=add( mul(f[i-1][j], j+1) , mul( f[i-1][j-1] , i-j) );
}
}
// PRi2D(f,10,10);
int n,k;
while(cin>>n>>k)
cout<<f[n][k]<<endl;
return 0;
}

UVA 11139 Counting Quadrilaterals

题意：求n*n的网格图(n+1行点），可以连出多少网格四边形(n<=120)
SP：本题允许O(n^4)做法

根据前面几题的做法
求总数，3点共线的情况，4点共线的情况，凹4边形（三角形里含一个点）的情况，容斥

Pick定理：格点多边形面积=内部整点数+1-边上整点数/2

令cnta,b表示外接矩形为a*b的三角形，内部的点的和

在平面上随机取3个整点构成的三角形，一定有一个点最靠边（横纵坐标均在其它2点的同侧）
所以可以枚举这个点并通过水平对称，垂直对称，遍历所有整点3角形（会有重复的）

凹四边形的解法，假设(0,0)O点选，枚举另外2点（假设在右下侧），且是向左拐的（有向面积 >0)，然后我们得到了一个三角形，
接下来考虑如何不重不漏

情况

情况

计入

两条边平行x,y轴，有3个靠边点

∠O为锐角2次，直角1次

需要计入4次

恰有一条边平行x,y轴的三角形，若为等腰三角形则这条边不是底边，2个靠边点

2次

需要计入4次

恰有一条边平行x,y轴的三角形，且这条边为等腰三角形的底边，2个靠边点

1次

需要计入2次

没有一条边平行x,y轴的三角形，有2个靠边点

2次

需要计入4次

没有一条边平行x,y轴的三角形，有1个靠边点

1次

需要计入4次

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case %d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[i]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll C(ll n,ll m) {
if (n==m||0==m) return 1;
if (n<m) return 0;
ll p=1;
Rep(i,m) p=p*(n-i)/(i+1);
return p;
}
#define MAXN (130)
ll g[MAXN][MAXN]={0};
int ABS(int a){
if (a>0) return a;return -a;
}
ll gcd(ll a,ll b){if (!b) return a;return gcd(b,a%b);}
ll calc(int a,int b,int c,int d){
ll S = (a*d-b*c)/2;
if(S<0) S=-S;
ll B = g[a][b] + g[c][d] + g[ABS(a-c)][ABS(b-d)];
return S + 1 - B /2;
}
ll cnt[MAXN][MAXN]={0}; // 表示长宽为i,j的矩形的所有内接三角形的里面的点的个数和
const int maxn = 122;
ll work() {
Rep(i,122)
Rep(j,122)
g[i][j]=gcd(i,j);
Rep(i,maxn)
Rep(j,maxn)
Rep(k,maxn)
Rep(l,maxn) {
if (j*k-i*l<=0) break;
int a=max(i,k),b=max(j,l);
ll tmp=calc(i,j,k,l);
ll p;
if (i==0 || k==0) {
if (j!=l) p=2;
else p=1;
}else if (j==0 || l==0) {
if (i!=k) p=2;
else p=1;
} else if ((i==a && j== b) || (k == a && l == b)) p=2;
else p=4;
cnt[a][b]+=tmp*p;
}
}

int n;
int main()
{
// freopen("uva11139.in","r",stdin);
// freopen(".out","w",stdout);
work();
while(cin>>n&&n) {
n++;
ll ans=C(n*n,4)-2LL*C(n,3)*n*(n*n-3)+3LL*2*C(n,4)*n;
For(i,n-1) For(j,n-1) {
ans -= (ll)2LL* (g[i][j]-1) * (n-i)*(n-j)*(n*n-3);
ans += (ll)3LL* 2 * C(g[i][j]-1,2) * (n-i)*(n-j);
}
For(i,n-1) For(j,n-1)
ans += 2LL*cnt[i][j]*(n-i)*(n-j);
printf("%d %lld\n",n-1,ans);
}


return 0;
}

UVA 1425 Metal

题意：平面上有n≤50个点,每个点x坐标不同，统计有多少种方法把它们连成一个单调多边形，单调多边形是指，如果把多边形看成实心物体，该物体任意竖线的相交部分是单点或一条线段。

从左往右枚举
状态用最后一个点与之前某个点相连转移

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
class P{
public:
ll x,y;
P(ll x=0,ll y=0):x(x),y(y){}
friend ll Cross(P A,P B) {return A.x*B.y-A.y*B.x; }
friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); }
friend bool operator<(P a,P b){return a.x<b.x; }

}p[MAXN];
int dp[MAXN][MAXN],n;
ll sgn(ll x){ return (!x)?(0):((x>0)?1:-1);}
int judge(int i,int j){ //i+1..j这段的折线 是否与线段i,j+1相交
int sg=sgn(Cross(p[j+1]-p[i],p[i+1]-p[i]));
Fork(k,i+1,j-1)
if (sg!=sgn(Cross(p[j+1]-p[i],p[k+1]-p[i]))) return 0;
return sg; //0 不合法
}
ll solve() {
MEM(dp)
dp[1][2]=dp[2][1]=1;
For(i,n) {
int k=i-1;
For(j,k-1) {
dp[i][j] +=dp[k][j];
dp[j][i] +=dp[j][k];
int p=judge(j,k);
if (p==1) dp[k][i] +=dp[k][j];
if (p==-1) dp[i][k] +=dp[j][k];
}

}

ll ans=0;

For(i,n) {
int p=judge(i,n-1);
if (p==1) ans+=dp[n][i];
if (p==-1) ans+=dp[i][n];
}
return ans;
}

int main()
{
// freopen("uva1425.in","r",stdin);
// freopen(".out","w",stdout);

int T=read();
while(T--) {
n=read();
For(i,n) cin>>p[i].x>>p[i].y;
sort(p+1,p+1+n);
cout<<solve()<<endl;
}



return 0;
}

HDU 3723 Delta Wave, Tianjin 2010

有一条折线，起点(0,0),终点(n,0)，每向右延伸一个单位长度，高度要么加1，要么减一，要么不变，问符合条件的线段数量？

import java.io.*;
import java.util.*;
import java.math.*;

public class Main
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n;

while(cin.hasNextInt())
{
n = cin.nextInt();
BigInteger ans = BigInteger.ONE;
BigInteger tmp=BigInteger.ONE;
for(int i=0;i<n/2;i++) {
tmp=tmp.multiply(BigInteger.valueOf(n-2*i)).multiply(BigInteger.valueOf(n-2*i-1))
.divide(BigInteger.valueOf(i+1)).divide(BigInteger.valueOf(i+2));
ans=ans.add(tmp);
}
System.out.println(ans.mod(BigInteger.TEN.pow(100)));
}
}
}

25补题

LA 3357,UVA 1350 Pinary, Seoul 2005

2进制中没有连续1的正整数，第2<k<9∗107大是多少？
找规律，发现长度为l且2进制中没有连续1的正整数恰有fib(l)个，
然后贪心每次贪最高位就行。
注意LA上java要快速输出不然会T
PS:UVA上Submission error 不知道为什么

import java.io.*;
import java.util.*;
public class Main
{
private static Writer writer = null;

public static void main(String args[])
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
writer = new OutputStreamWriter(System.out);
int n;
int MAXN = 41;
int fib[] = new int[MAXN];
int sum[] = new int[MAXN];
int ans[] = new int[MAXN];

sum[0]=fib[0]=0;
fib[1]=fib[2]=1;
int m=38;
for(int i=3;i<=m;i++) {
fib[i]=fib[i-1]+fib[i-2];
}
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+fib[i];
int T=cin.nextInt();
for(int kcase=1;kcase<=T;kcase++)
{
n = cin.nextInt();
for(int i=1;i<=m;i++) ans[i]=0;
for(int i=m;i>0;i--) {
if (sum[i-1]<n&&n<=sum[i]) {
ans[i]=1;
n=n-sum[i-1]-1;
}
}
int p=m;
while (0 == ans[p]) --p;
try {
for(;p>0;p--) writer.write(ans[p]+"");
writer.write("\n");
writer.flush();
} catch

UVA 12075 Counting Triangles

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll C(ll n) {
return n*(n-1)*(n-2)/6;
}
ll gcd(ll a,ll b){if (!b) return a;return gcd(b,a%b);}
#define
ll f[MAXN][MAXN]={0};
int main()
{
// freopen("uva12075.in","r",stdin);
// freopen(".out","w",stdout);


int m,n;
int kcase=0;
while(cin>>m>>n && m && n ) {
ll ans=C((m+1)*(n+1))-C(m+1)*(n+1)-C(n+1)*(m+1);
For(i,m) For(j,n) {
ans -= 2LL*(m+1-i)*(n+1-j)*(gcd(i,j)-1);
}
Pr(++kcase,ans)
}


return 0;
}


上一篇：【二叉树】另一个二叉树的子树
下一篇：没有了
网友评论
相关栏目
最近更新
热门文章