1009 Sparse Graph（hdu5876）
由于每条边的权值都为1，所以最短路bfs就够了，只是要求转置图的最短路，所以得用两个set来维护，一个用来存储上次扩散还没访问的点，一个用来存储这一次扩散还没访问的点。
算法：bfs+set
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
#include<stack>
#include<set>
using namespace std;
const int maxn=;
const int INF=0x3f3f3f3f;
int t,n,m,u,v;
int head[maxn];int tot;
int di[maxn];
struct Edge
{
int to,next;
}edge[maxn];
void init()
{
tot=;
memset(head,-,sizeof(head));
}
void add(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
struct node
{
int num,dis;
}; void bfs(int beg)
{
set<int>s,e;
set<int>::iterator it;
queue<node>q;
for(int i=;i<=n;i++)
s.insert(i),di[i]=INF;
node temp,nex;
temp.num=beg,temp.dis=;
q.push(temp);
s.erase(beg);
while(!q.empty())
{
temp=q.front();q.pop();
for(int i=head[temp.num];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(s.find(v)==s.end())
continue;
s.erase(v);e.insert(v);
}
for(it=s.begin();it!=s.end();it++)
{
nex.num=*it;nex.dis=temp.dis+;
di[nex.num]=min(nex.dis,di[nex.num]);
q.push(nex);
}
s.swap(e);e.clear();
}
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(int i=;i<m;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
int pos;
scanf("%d",&pos);
bfs(pos);
if(n!=pos){
for(int i=;i<=n;i++)
{
if(i==pos)continue;
if(i!=n)
printf("%d ",di[i]!=INF?di[i]:-);
else
printf("%d\n",di[i]!=INF?di[i]:-);
} }else{
for(int i=;i<=n-;i++)
{
if(!=(n-))
printf("%d ",di[i]!=INF?di[i]:-);
else
printf("%d\n",di[i]!=INF?di[i]:-);
} }
}
return ;
}
1010 Weak Pair（hdu5877）
题意是要求所有节点的权值与其祖先节点权值相乘小于或等于k的总共有多少对，一开始知道必须得进行dfs，也知道可以马上建一个数组b[n]来记录每个节点需要和小于多少的数相乘才会小于看，但是在查询有多少个祖先节点小于b[i]时没有找到方法，后来才知道，可以将数据离散化后存进树状数组，只保留当前节点的父节点在树状数组当中，一旦离开这个节点，就把这个节点的权值在树状数组中删除
算法：dfs+离散化+BIT
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
const int maxn=;
int n;
ll k,a[maxn];
vector<int>son[maxn];
ll ran[maxn];
ll b[maxn];
int in[maxn];
ll B[maxn];
int low_bit(int x)
{
return x&(-x);
}
ll Sum(int x){
ll s1 = ;
while (x) s1 += B[x], x -= low_bit(x);
return s1;
}
void Add(int x, int d){
while (x<=n) B[x] += d,x += low_bit(x);
}
void init(int n)
{
for(int i=;i<=n;i++){
son[i].clear();
}
memset(in,,sizeof(in));
}
ll dfs(int rt)
{
Add(ran[rt],);
ll ans=;
for(int i=;i<son[rt].size();i++){
int nex=son[rt][i];
ans+=dfs(nex);
}
Add(ran[rt], -);
ll num=upper_bound(a+,a++n,b[rt])-a-;
ans+=Sum(num);
return ans;
}
int main()
{
//freopen("input.txt","r",stdin);
int t; scanf("%d", &t);
while(t--)
{
scanf("%d%lld",&n,&k);
init(n);
for(int i=;i<=n;i++){
scanf("%lld",&a[i]);
ran[i] = a[i];
if (a[i] != )
b[i] = k / a[i];
else
b[i] = ;
} int u,v;
for(int i=;i<=n-;i++){
scanf("%d%d",&u,&v);
son[u].push_back(v);
in[v]++;
}
sort(a+,a++n);
unique(a+,a++n);
for(int i=;i<=n;i++){
ran[i]=lower_bound(a+,a+n+,ran[i])-a;
}
int root=;
for(int i=;i<=n;i++){
if(in[i]==)
root=i;
}
ll ans=dfs(root);
printf("%lld\n",ans);
}
return ;
}
1001 Different Circle Permutation
题意：1条项链有n个珠子，有黑白2种颜色，求任意2个黑珠不相邻的项链的种类数（旋转同构）
由于有黑珠不能相邻的条件，burnside或polya不能套用。不过自己计算不考虑旋转同构的方案数就会发现：
设f(n)为n个珠子涂色使得黑珠左右不相邻的方案数，则f(n)=f(n-1)+f(n-2)其中f(1)=1 f(2)=3
可以理解为前者是1个白珠子接上n-1个珠子，后者是1个黑珠子接上1个白珠子再接n-2个珠子（出现最右1个是黑珠的情况，把最左黑珠与右边互换，还是不同方案）
至于如何求旋转同构时的方案数，把n个珠子按照1,2,3,4...u,1...这个编号平均分成n/u份，每份都是按照原先左右关系连接后满足黑珠不相邻的，所以这部分方案数是f(u)
要满足这个，首先n%u==0，那旋转k个珠子的角度实际上是分割为每份gcd(k,n)
根据burnside引理，n种珠子排布，在k种旋转后相同视为同构，方案数是（这n种珠子排布分别做k种旋转后还是同样排布的数量之和）/k
所以方案数是∑(f( gcd(i,n) ))/n ( 1<=i<=n)
思维出来了，程序也容易写了
由于n可达10的9次方，暴力计算会超时
其实可以合并的，根据欧拉函数的定义可以合并为(1<=i<=n)∑(f( gcd(i,n) ))/n=(d|n)∑f(d)*euler(n/d)
f(d)可以矩阵快速幂得出，euler(d)由于实在太大应该分解质因子做
其实这2种运算都可以在一个合理的范围内打表，小的直接查表得出
欧拉函数也用不着分解到底
算法：矩阵幂+欧拉函数运算
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+ ;
struct matrix {
long long x1,x2 ;
long long x3,x4 ;
}; matrix mul(matrix a,matrix b){
matrix ans ;
ans.x1 = (a.x1*b.x1 + a.x2*b.x3)%mod ;
ans.x2 = (a.x1*b.x2 + a.x2*b.x4)%mod ;
ans.x3 = (a.x3*b.x1 + a.x4*b.x3)%mod ;
ans.x4 = (a.x3*b.x2 + a.x4*b.x4)%mod ;
return ans ;
} long long quick_matrix(long long x){
x -= ;
matrix ans,cal ;
ans.x1 = ans.x2 = ans.x3 = ; ans.x4 = ;
cal.x1 = cal.x2 = cal.x3 = ; cal.x4 = ;
while (x){
if (x%)
ans = mul(ans,cal) ;
cal = mul(cal,cal) ;
x >>= ;
}
return (ans.x1*+ans.x2*)%mod ;
} long long fx(long long x){
if (x == )
return ;
else if (x == )
return ;
else if (x == )
return ;
else return quick_matrix(x) ;
} long long quick(long long a,long long n){
long long ans = ;
long long cal = a ;
while (n){
if (n%)
ans = (ans*cal)%mod ;
cal = (cal*cal)%mod;
n >>= ;
}
return ans ;
} long long euler(long long n)
{
long long ans = n;
long long i;
for (i = ; i*i <= n; i++){
if (n%i == ){
while (n%i == )
n /= i;
ans = ans/i*(i-) ;
}
}
if (n != )
ans = ans/n*(n-);
return ans;
} long long solve(long long n){
if (n == )
return ;
long long ans = ;
long long nn = n ;
long long d;
long long i;
for (i = ; i*i < n; i++){
if (n%i == ){
ans = (ans + fx(i)*euler(nn/i) + fx(nn/i)*euler(i))%mod ;
}
}
if (i*i == n)
ans = (ans + fx(i)*euler(i))%mod ;
return (ans*quick(nn,mod-))%mod;
} int main()
{
long long n;
while (~scanf("%lld",&n))
printf("%lld\n",solve(n)) ;
return ;
}
hdu5868
1002 Different GCD Subarray Query
题意：求Q个区间含有不同的连续序列gcd个数，例如(6,8,12) gcd(6)=6 gcd(8)=8 gcd(12)=12 gcd(6,8)=2 gcd(8,12)=4 gcd(6,8,12)=2 含5种gcd值
固定右边界，左边界越往左，连续序列gcd值越小，并且两个数要么相等，要么至少相差1倍，所以一个右边界最多延伸出logn种gcd值。
题目可以离线做，合并相同右边界的查询，预处理出n个右边界的逆序对应gcd值。
树状数组储存最右出现的gcd值种类数
查询时把相同gcd值最先出现的位置尽量往右移，这样区间查询就不会减去[1,l-1]和[l,r]都含有的并且最先出现在[l,r]的数字
算法：离线+BIT
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#define lowbit(x) (x & (-x))
using namespace std;
typedef __int64 ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + ; int a[MAXN];
int ans[MAXN];
vector<pii> gc[MAXN];
vector<pii> query[MAXN]; int vis[MAXN * ];
int n,q; int __gcd(int a,int b){return b?__gcd(b,a%b):a;}
int sum[MAXN];
void treeinit(){memset(sum,,sizeof(sum));} void update(int x,int v){while(x <= n){sum[x] += v;x += lowbit(x);}} int getSum(int x){int ans = ;while(x){ans += sum[x];x -= lowbit(x);}return ans;} void init(){
for (int i = ;i <= n;i ++){
gc[i].clear();
query[i].clear();
}
memset(vis,,sizeof(vis));
treeinit();
} void input(){
int i,j;
for (i = ;i <= n;i ++)
scanf("%d",a + i);
//统计不同右边界从右到左的连续相同gcd值，O(nlog2n)
//这里还有一种方法，预先处理出RMQ再O(nlog2nlog2n)二重二分
for (i = ;i <= n;i ++){
int x = a[i];
int y = i; for (j = ; j < gc[i - ].size();j ++){
int res = __gcd(gc[i - ][j].first,x);
if (x != res){
gc[i].push_back(make_pair(x,y));
x = res; y = gc[i - ][j].second;
}
} gc[i].push_back(make_pair(x,y));
} for (i = ;i <= q;i ++){
int l,r;
scanf("%d%d",&l,&r);
query[r].push_back(make_pair(l,i));
}
//查询区间不同数的数量，右边界到哪加到哪
for (i = ;i <= n;i ++){
//这里的思路，不是想着把查询分成1个三角形和一个直角梯形（事实证明这个思路有些复杂）
//是把不同种类的数映射位置后放在数组上(若有重复则把数右移），以备区间查询
for (j = ;j < gc[i].size();j ++){
int res = gc[i][j].first;
int ind = gc[i][j].second; if (vis[res])//有相等的数则把数的头标签往右移
update(vis[res],-);
vis[res] = ind;
update(ind,);
} for (j = ;j < query[i].size();j ++){
int l = query[i][j].first;
int ind = query[i][j].second; ans[ind] = getSum(i) - getSum(l - ); } } for (i = ;i <= q;i++){
printf("%d\n",ans[i]);
}
} int main(){
while(scanf("%d%d",&n,&q)!=EOF){
init();
input();
}
return ;
}
hdu5869
1005 Seats
题意：有m个部门（部门数和分别的学生数不确定），部门学生数不确定，但一定不大于h，整个学校学生数L人，会场一排k个座位且L%k==0。问在任何情况下都能让同部门的学生一定坐一排的最少座位排数。
要让这些学生占据最多的行，就是说每行座位的空位正好无法再坐一个部门，比较简单的做法：先求出部门数较多的情况下空位最少时，每排部门数=k/h，那要让空位最多，并且让1个部门学生多得不能再坐，那能坐满排时1个部门学生数=k/(k/h+1)，让1排空出最多的位需要1个部门有且仅有r=k/(k/h+1)+1，那样每排部门数又是k/h，每排最少要排k-k%r，剩下的人可以另起1行或安排到其他排的空位上（但是他喵的数据错误了，后者的情况下把人塞到其他排会WA）
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 1123456
using namespace std;
long long n,m,sum,res,flag;
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.txt","r",stdin);
#endif
long long i,j,cas,T,t,x,y,z,h,l,k;
while(scanf("%I64d%I64d%I64d",&h,&l,&k)!=EOF)
{
x=k/h;//最大人数时一排几个部门
y=k/(x+);//多放一个部门时每个部门最多的人数
res=y+;//加一个人保证不能多放一个部门
printf("%I64d\n",l/(k-k%res)+bool(l%(k-k%res)));//不是正解，数据正确的话会WA
}
return ;
}
1006 football game
题意不多说。
定理什么的，可以理解为n个人比赛，胜得2分平得1分，那n人总分就是n(n-1)
排序，再计算前q人的总分，由于没人的分数是负数，如果前q人总分超q(q-1)就不合理
最后的总分也必须是n(n-1)
#include<bits/stdc++.h>
using namespace std;
const int maxn = +;
int n,a[maxn];
int main()
{
int T;
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
int res = ;
scanf("%d",&n);
for(int i = ;i<=n;i++)
scanf("%d",&a[i]),res+=a[i];
sort(a+,a++n);
int sum = ;
int flag = ;
for(int i = ;i<=n;i++)
{
sum+=a[i];
if(sum<i*(i-))
{
flag=;
break;
}
}
if(res!=n*(n-))
flag=;
if(flag)
printf("F\n");
else
printf("T\n");
}
}
}
1007 friends and emenies
脑洞多一点的人会想到把互为朋友的1对关系当成1对连边
如果3人互为朋友，那为3人的3对关系找3种珠子不如给3人1种珠子，相当于三元环
所以问题其实是n个点，没有三元环并且互相连通的图最多边数
没有三元环，就是说可以形成二分图；最多边数，就是说2个点集点数相差最小
边数n/2*(n-n/2)
再比较下实际有的珠子种类数就ok了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL m,n;
while(~scanf("%I64d %I64d",&m,&n))
{
LL ans = m/*(m-m/); if( ans <= n) puts("T");
else puts("F");
}
return ;
}
1008 function
与1002差不多，都是那种1个左（右）边界对应logn种（m%n可能是m，也可能是小于m/2的某个数）数的题目
还是一样，离线查询，把所有的区间求出来，注意合并
不过这次不用事先求出所有对
并且储存方式也改为优先队列以防止多余处理（能模到小于原数的要入队，不能的不处理）
在右边界向右推进的同时更新对应左边界对应数
算法：离线+优先队列
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = + ;
typedef pair<int, int> Pair;
int ans[maxn], L[maxn];
vector<Pair> R[maxn]; //(L, id)
priority_queue<Pair> cal; //(num, pos) int main()
{
int T, cas=, n;
scanf("%d", &T);
while(T--)
{
while(!cal.empty()) cal.pop();
for(int i=;i<maxn;++i) R[i].clear(); scanf("%d", &n);
for(int i=;i<=n;++i) scanf("%d", &L[i]);
int l, r, q;
scanf("%d", &q);
for(int i=;i<=q;++i)//把所有右边界相等的元素归一起，这是只有区间查询时的常用策略
{
scanf("%d%d", &l, &r);
R[r].push_back(make_pair(l, i));
} for(int i=;i<=n;++i)
{
int l, r;
//处理能改变结果的查询，用堆防止过多访问变成O(n^2)
//注意1个左边界最多得到O(log2n)种结果
while(!cal.empty()&&cal.top().first>=L[i])
{
l = cal.top().second;
r = i;
L[l] = cal.top().first%L[i];
cal.pop();
cal.push(make_pair(L[l], l));
}
cal.push(make_pair(L[i], i));
for(int j=;j<R[i].size();++j)
{
l = R[i][j].first;
ans[R[i][j].second] = L[l];
}
}
for(int i=;i<=q;++i) printf("%d\n", ans[i]);
} return ;
}
hdu5875