1001 p-1的因子个数。
#include <bits/stdc++.h>
using namespace std;
int T,P;
int check(int x) {
int ret=0;
for (int i=1;i*i<=x;++i) {
if (x%i==0) {
++ret;
if (x/i!=i)
++ret;
}
}
return ret;
}
int main()
{
cin>>T;
while (T--) {
cin>>P;
cout<<check(P-1)<<endl;
}
return 0;
}
1002 先倍增区间端点，再二分+并查集 check
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int L,f[maxn],a[maxn],b[maxn],e[maxn];
vector<int> ans;
int F(int x) {
return x==f[x]?x:f[x]=F(f[x]);
}
void U(int a,int b) {
f[F(a)]=F(b);
}
bool check(int l,int r) {
for (int i=l;i<=r;++i)
f[a[i]]=a[i],f[b[i]]=b[i];
for (int i=l;i<=r;++i)
if (e[i]==1)
U(a[i],b[i]);
for (int i=l;i<=r;++i)
if (e[i]==0&&F(a[i])==F(b[i]))
return false;
return true;
}
int main()
{
scanf("%d",&L);
for (int i=0;i<L;++i)
scanf("%d%d%d",&a[i],&b[i],&e[i]);
int l=0;
while (l<L) {
int x=0;
while (l+(1<<x)-1<L&&check(l,l+(1<<x)-1))
++x;
int left=l,right=min(L-1,l+(1<<x)-1),res=-1;
while (left<=right) {
int mid=(left+right)>>1;
if (!check(l,mid)) {
res=mid;
right=mid-1;
} else
left=mid+1;
}
ans.push_back(res-l+1);
l=res+1;
}
printf("%d\n",ans.size());
for (int i=0;i<(int)ans.size();++i)
printf("%d\n",ans[i]);
return 0;
}
1003 线段树维护路径交
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,long long> pil;
const int maxn=500005;
int q,n,m,f[20][maxn];
long long dep[maxn],level[maxn];
vector<pil> G[maxn];
void dfs(int u,int fa,long long d,int l) {
dep[u]=d;
level[u]=l;
f[0][u]=fa;
for (int i=0;i<(int)G[u].size();++i) {
int v=G[u][i].first;
if (v==fa)
continue;
dfs(v,u,d+G[u][i].second,l+1);
}
}
inline void init() {
f[0][1]=1;
for (int i=1;i<20;++i)
for (int j=1;j<=n;++j)
f[i][j]=f[i-1][f[i-1][j]];
}
inline int lca(int a,int b) {
if (level[a]<level[b])
swap(a,b);
int det=level[a]-level[b];
for (int i=0;i<20;++i)
if (det&(1<<i))
a=f[i][a];
if (a==b)
return a;
for (int i=19;i>=0;--i)
if (f[i][a]!=f[i][b]) {
a=f[i][a];
b=f[i][b];
}
return f[0][a];
}
inline int MAX(int a,int b) {
if (dep[a]>dep[b])
return a;
return b;
}
struct node {
int a,b;
node(){}
node(int a,int b):a(a),b(b){}
inline node operator+(const node &rhs)const{
int ta=MAX(lca(a,rhs.a),lca(a,rhs.b));
int tb=MAX(lca(b,rhs.a),lca(b,rhs.b));
return node(ta,tb);
}
} seg[maxn<<2];
inline void pushup(int x) {
seg[x]=seg[x<<1]+seg[x<<1|1];
}
void build(int x,int l,int r) {
if (l==r) {
scanf("%d%d",&seg[x].a,&seg[x].b);
return;
}
int m=(l+r)>>1;
build(x<<1,l,m);
build(x<<1|1,m+1,r);
pushup(x);
}
node query(int x,int L,int R,int l,int r) {
if (l<=L&&r>=R)
return seg[x];
int m=(L+R)>>1;
if (m<l)
return query(x<<1|1,m+1,R,l,r);
if (m>=r)
return query(x<<1,L,m,l,r);
return query(x<<1,L,m,l,r)+query(x<<1|1,m+1,R,l,r);
}
int main()
{
while (scanf("%d",&n)==1) {
for (int i=1;i<=n;++i)
G[i].clear();
for (int i=0;i<n-1;++i) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
G[x].push_back(pil(y,z));
G[y].push_back(pil(x,z));
}
dfs(1,-1,0,0);
init();
scanf("%d",&m);
build(1,1,m);
scanf("%d",&q);
while (q--) {
int l,r;
scanf("%d%d",&l,&r);
node t=query(1,1,m,l,r);
printf("%I64d\n",dep[t.a]-2LL*dep[lca(t.a,t.b)]+dep[t.b]);
}
}
return 0;
}
1004 bfs
#include <bits/stdc++.h>
using namespace std;
const short dx[4]={-1,1,0,0};
const short dy[4]={0,0,-1,1};
int T,n,m,sx,sy,res;
char s[64][65];
inline id(int x,int y) {
return x*m+y;
}
struct node {
short x,y;
long long st;
bool key;
node(){}
node(short x,short y,long long st,bool key):x(x),y(y),st(st),key(key){}
bool operator<(const node &rhs)const{
if (id(x,y)!=id(rhs.x,rhs.y))
return id(x,y)<id(rhs.x,rhs.y);
else if (st!=rhs.st)
return st<rhs.st;
return key<rhs.key;
}
};
queue<node> que;
map<node,short> mp;
bool check(int x,int y,long long st,char ch) {
int cnt=0;
for (int i=0;i<4;++i) {
int tx=x+dx[i],ty=y+dy[i];
if (tx<0||tx>=n||ty<0||ty>=m)
continue;
if ((st>>id(tx,ty))&1)
++cnt;
}
if (((cnt&1)&&(ch!='x'))||(!(cnt&1)&&ch=='x'))
return false;
return true;
}
int main()
{
scanf("%d",&T);
for (int cas=1;cas<=T;++cas) {
while (!que.empty())
que.pop();
mp.clear();
scanf("%d%d",&n,&m);
for (int i=0;i<n;++i)
scanf("%s",s[i]);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j)
if (s[i][j]=='S')
sx=i,sy=j;
que.push(node(sx,sy,0LL,false));
mp[node(sx,sy,0LL,false)]=0;
res=-1;
while (!que.empty()) {
short x=que.front().x,y=que.front().y;
long long st=que.front().st;
bool key=que.front().key;
if (s[x][y]=='E'&&key) {
res=mp[que.front()];
break;
}
que.pop();
for (int i=0;i<4;++i) {
int tx=x+dx[i],ty=y+dy[i];
if (tx<0||tx>=n||ty<0||ty>=m||!check(tx,ty,st,s[tx][ty]))
continue;
long long nst=(s[tx][ty]=='*')?(st^(1LL<<id(tx,ty))):st;
bool nkey=(s[tx][ty]=='K')?true:key;
if (mp.find(node(tx,ty,nst,nkey))!=mp.end())
continue;
mp[node(tx,ty,nst,nkey)]=mp[node(x,y,st,key)]+1;
que.push(node(tx,ty,nst,nkey));
}
}
printf("Case #%d:\n%d\n",cas,res);
}
return 0;
}
1005 轻量级模拟
#include <bits/stdc++.h>
using namespace std;
const int Month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int T,year,month,day,yday[10005],now;
int ok(int x) {
if ((x%4==0&&x%100!=0)||x%400==0)
return 1;
return 0;
}
void init() {
for (int i=1;i<=10000;++i)
yday[i]=yday[i-1]+365+ok(i);
}
int check(int x) {
if (!ok(x)&&month==2&&day==29)
return now+1;
int ret=yday[x-1];
for (int i=1;i<month;++i) {
if (i==2&&ok(x)==1)
++ret;
ret+=Month[i];
}
return ret+day;
}
int main()
{
init();
scanf("%d",&T);
while (T--) {
scanf("%d-%d-%d",&year,&month,&day);
now=check(year);
for (int i=year+1;;++i) {
if ((check(i)-now)%7==0) {
printf("%d\n",i);
break;
}
}
}
return 0;
}
1006 轻量级模拟
#include <bits/stdc++.h>
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
int n,m,vis[105][105];
char s[105][105];
void dfs(int x,int y,char ch) {
if (x<0||x>n+1||y<0||y>m+1||vis[x][y]==1||s[x][y]!=ch)
return;
vis[x][y]=1;
for (int i=0;i<4;++i)
dfs(x+dx[i],y+dy[i],ch);
}
int main()
{
while (scanf("%d%d",&n,&m)==2&&n+m>0) {
memset(vis,0,sizeof vis);
memset(s,'0',sizeof s);
for (int i=1;i<=n;++i) {
scanf("%s",s[i]+1);
s[i][m+1]='0';
}
int cnt=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (!vis[i][j]&&s[i][j]=='1') {
dfs(i,j,'1');
++cnt;
}
if (cnt!=1) {
puts("-1");
continue;
}
cnt=0;
for (int i=0;i<=n+1;++i)
for (int j=0;j<=m+1;++j)
if (!vis[i][j]&&s[i][j]=='0') {
dfs(i,j,'0');
++cnt;
}
if (cnt==1)
puts("1");
else if (cnt==2)
puts("0");
else
puts("-1");
}
return 0;
}