NOIP模拟题 2016.11.2 [数论]

T1：水题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=;
const int maxn = ;
char S[maxn],T[maxn];
stack <int> sta;
inline void print_bad()
{
    puts("No");
    exit();
}
inline void print_good()
{
    puts("Yes");
    while(!sta.empty()) printf("%d\n",sta.top()),sta.pop();
}
int main()
{
    freopen("door.in","r",stdin);
    freopen("door.out","w",stdout);
    scanf("%s%s",S+,T+);
    int pS = strlen(S+);
    int pT = strlen(T+);
    while(true)
    {
        if(!pT) break;
        if(!pS) print_bad();
        if(S[pS] == T[pT]) sta.push(pS),pT--;
        pS--;
    }
    print_good();
    return ;
}
           

T2：注意建图时的常数优化。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=;
const int maxn = ;
const int maxm = ;
const int V = * + ;
const int E = * + ;
struct Edge
{
    int to,next;
}edge[E];
int head[V];
int maxedge;
inline void addedge(int u,int v)
{
    edge[++maxedge] = (Edge) { v,head[u] };
    head[u] = maxedge;
}
int deg[V];
bool vis[V];
void dfs(int u)
{
    vis[u] = true;
    for(int i=head[u];~i;i=edge[i].next)
    {
        int v = edge[i].to;
        deg[v]++;
        if(vis[v]) continue;
        dfs(v);
    }
}
bool g[maxn][maxm];
int id[maxn][maxm];
int n,m;
int maxnode;
int cost[V];
int S;
void init()
{
    memset(head,-,sizeof(head)); maxedge=-;
    memset(g,,sizeof(g));
    S = maxnode = ;
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            char ch = (char) getchar();
            while(!isdigit(ch)) ch = (char) getchar();
            g[i][j] = (ch=='1');
        }
    for(int j=;j<=m;j++) g[][j] = false , id[][j] = maxnode;
    for(int i=;i<=n;i++) if(!(i&))
        for(int j=;j<=m;j++) if(!g[i][j])
            if(g[i][j-]) id[i][j] = ++maxnode , cost[maxnode]=;
            else id[i][j] = maxnode , cost[maxnode]++;
    for(int i=;i<=n;i++) if(i&)
    {
        for(int j=;j<=m;j++) if(!g[i][j])
        {
            if(g[i-][j] || g[i+][j]) continue;
            addedge(id[i-][j],id[i+][j]);
        }
    }
    dfs(S);
}
queue <int> que;
int dis[V];
void spfa(int S)
{
    que.push(S); dis[S]=;
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        for(int i=head[u];~i;i=edge[i].next)
        {
            int v = edge[i].to;
            smax(dis[v],dis[u]+cost[v]);
            if(--deg[v] == ) que.push(v);
        }
    }
}
int work()
{
    spfa(S);
    int ans = -;
    for(int j=;j<=m;j++) if(!g[n][j])
        smax(ans,dis[id[n][j]]);
    return !ans?-:ans;
}
int main()
{
    freopen("ant.in","r",stdin);
    freopen("ant.out","w",stdout);
    init();
    int ans = work();
    printf("%d",ans);
    return ;
}
           

T3：数论。

关键在于已知勾股数组(a,b,c)中的c，要求快速求出所有的a,b。

根据勾股数的性质来枚举b,c的差是不可取的，因为中间有重复的情况。。

设勾股数为(a,b,r)，那么b = sqrt( (r-a)*(r+a) )

令 d = gcd( r-a,r+a ) ，A = (r-a)/d , B = (r+a)/d ，那么显然gcd(A,B)=1 且 A!=B.

由此可以推出b = d * sqrt(AB) ， 并且A B 都是完全平方数。

这样设 A = x*x , B = y*y ，显然 x!=y

由于 A +Ｂ = 2r/d ， 即 x*x + y*y = 2r/d

并且对于不同的d，(a,b)是不同的，那么可以用O(sqrt(2r))枚举d，把所有的答案直接加起来，没有重复。

对于d <= sqrt(2r)的那个因数，和d > sqrt(2r)的那个因数分别更新答案。

注意gcd(x,y)==1

注意限制 a < b以免重复枚举。

理论时间复杂度在O(4e8)左右，但是对于不是因数的d，根本不会去枚举x，所以有大量的剪枝。。。

具体细节见代码，还算清晰。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
typedef long long LL;
template <class T> T gcd(T a,T b) { return !b?a:gcd(b,a%b); }
LL N,M;
inline void add(LL &ans,LL x,LL y)
{
    if(N-x>= && M-y>=) ans += (N-x)*(M-y)*;
    if(M-x>= && N-y>=) ans += (M-x)*(N-y)*;
}
int main()
{
    freopen("amount.in","r",stdin);
    freopen("amount.out","w",stdout);
    int T;
    scanf(AUTO AUTO "%d",&N,&M,&T);
    while(T--)
    {
        LL W;
        scanf(AUTO,&W);
        LL ans = ;
        if(N-W>=) ans += M*(N-W);
        if(M-W>=) ans += N*(M-W);
        for(LL d=;d*d<=(W<<);d++) if((W<<)%d==) // d for 2R/d
        {
            LL D = (W<<)/d;
            for(LL x=;x*x<=(D>>);x++)
            {
                LL tmp = D - x*x;
                if(tmp<=) break;
                LL y = (LL)floor(sqrt(tmp));
                if(x*x+y*y!=D) continue;
                if(x == y) continue;
                if(gcd(x,y) ^ ) continue;
                LL a = W-x*x*d;
                LL b = d*x*y;
                if(a > b) continue;
                add(ans,a,b);
            }
            if(d*d == (W<<)) continue;
            D = d;          
            for(LL x=;x*x<=(D>>);x++)
            {
                LL tmp = D - x*x;
                if(tmp<=) break;
                LL y = (LL)floor(sqrt(tmp));
                if(x*x+y*y!=D) continue;
                if(x == y) continue;
                if(gcd(x,y) ^ ) continue;
                LL a = W-x*x*((W<<)/d);
                LL b = ((W<<)/d)*x*y;
                if(a > b) continue;
                add(ans,a,b);
            }
        }
        printf(AUTO,ans);
        putchar(' ');
    }
    return ;
}