2017沈阳站（重温经典）

• 导语
• 涉及的知识点
• 题目
• • F
  • G
  • I
  • K
  • L
  • M
• 参考文献

导语

到了铜牌区，但是离银牌还有一定距离，剩下的时间不多了，需要更加专注和更多的巩固

涉及的知识点

思维，搜索，大数运算

题目

F

题目大意：定义一种三角形，其边长分别为整数 t − 1 , t , t + 1 t-1,t,t+1 t−1,t,t+1并且三角形的面积是整数，给出一个整数 n n n，找出一个刚好大于 n n n的整数 t t t，使得构成的三角形符合定义

思路：找规律，首先根据给定数据计算三角形面积，带入海伦公式得 S = 3 × t 2 ( t 2 − 4 ) / 16 S=\sqrt{3×t^2(t^2-4)/16} S=3×t2(t2−4)/16 ​，由于面积为整数，可以得到方程 t 4 − 4 t 2 − 48 S 2 = 0 t^4-4t^2-48S^2=0 t4−4t2−48S2=0，可以打表带入 t t t计算 S S S，如果 S S S为整数则 t t t为解，打表可得通项公式 t i = 4 t i − 1 − t i − 2 t_i=4t_{i-1}-t_{i-2} ti​=4ti−1​−ti−2​，可以看到数据基本呈指数级增长，所以 1 0 30 10^{30} 1030范围内的有效解不会很多，直接用大数输入输出在线处理，递推到首个大于n的t即可

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
__int128 a[1000];
void scan(__int128 &x)//输入
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
void print(__int128 x)//输出
{
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
void solve()
{
    __int128 n,t1,t2;
    scan(n);
    t1=2;
    for(t2 = 4;t2<n;t2=t2*4-t1)
    {
        t1=t2;
    }
    print(t2);
    printf("\n");
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
    return 0;
}

G

题目大意：给出一个长度为n的由0-9构成的数字序列，下标为0 ~ n-1，从下标为i的点只能走到下标为(i*i+1)%n的点，选定一个起点走n次，记录每次走的数字，求出数字构造的最大字典序序列

思路：整体构造最大，那么每一位就尽量要最大，构造每一位必然就要搜索，将序列中最大数的下标统一存起来便于搜索，这里如果直接暴搜DFS一定会超时，为了更快的构造字符串并剪枝，采用BFS更合适
为了构造最大，每一次的选择最好是步数最小，当前位置值最大且最靠前的位置，值最大便于构造最大，位置靠前代表值在字符串的位置靠前，步数最小代表后面还有更多的可以选择的余地，那么根据这样的要求建堆即可，还要剔除重复的方案，如果两个点经过相同步数到达同一个点，那么其之后状态也一样，这样的方案只需算一次，详见代码

代码

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+5;
int T,val[maxn],n,x,ans[maxn],nt[maxn];
char s[maxn];
struct node {
    int step,pos;
    bool operator<(const node&a)const {
        if(step==a.step&&nt[pos]==nt[a.pos])return pos<a.pos;
        //步数相等，下一步相等，判断位置
        if(step==a.step)return nt[pos]<nt[a.pos];
        //步数相等，判断下一步
        return step>a.step;
        //判断步数
    }
};
signed main() {
    scanf("%lld",&T);
    for(int k=1; k<=T; k++) {
        scanf("%lld%s",&n,s);
        int mx=0;
        for(int i=0; i<n; i++) {
            val[i]=s[i]-'0';
            mx=max(mx,val[i]);//获取最大值
            ans[i]=-1;//初始化
        }
        for(int i=0; i<n; i++)
            nt[i]=val[(i*i+1)%n];//初始化下一步
        ans[n]=-1,ans[1]=mx;
        int pre=-1;
        priority_queue<node>q;
        for(int i=0; i<n; i++)
            if(val[i]==mx)q.push(node{1,i});//找到起始数字最大的位置进行BFS
        while(!q.empty()) {
            node t=q.top();//每次选出的必是步数最小，当前位置值最大且最靠前的位置
            q.pop();
            int pos=(t.pos*t.pos+1)%n,step=t.step+1;
            //下一个跳转的位置和步数
            if(ans[step]==-1) {//第一个跳到第step步
                q.push(node{step,pos});
                ans[step]=val[pos];//更新这一步的构造的字符串
                pre=pos;//记录上一个位置
            } else if(val[pos]==ans[step]) {//如果出现了其余位置跳转到同一个点
                if(pos!=pre) {//判断是否为同一个点，不是则说明可能有别的方案
                    q.push(node{step,pos});
                    pre=pos;
                }
            }
            if(ans[n]!=-1)break;//最后一个位置已经构造完成
        }
        printf("Case #%lld: ",k);
        for(int i=1; i<=n; i++)printf("%lld",ans[i]);
        putchar('\n');
    }
    return 0;
}

I

题目大意：计算四个最大为 2 62 2^{62} 262的正整数相加

思路：直接用int128计算即可

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
void scan(__int128 &x)//输入
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
void print(__int128 x)//输出
{
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
void solve()
{
    __int128 a,b,c,d,res;
    scan(a);
    scan(b);
    scan(c);
    scan(d);
    res = a+b+c+d;
    print(res);
    printf("\n");
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
    return 0;
}

K

题目大意：略

思路：以贪心的思路，分别尝试以左端点为基准插入右边整个大区间和以右端点为基准插入左边的整个大区间，最好的结果就是区间内所有的空格，分别求出空格数求极值即可

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int a[505];
void solve()
{
    int n,res=0;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",a+i);
    }
    res = max(res,a[n-1]-a[1]-1-n+3);
    res=max(res,a[n]-a[2]-1-n+3);
    printf("%d\n",res);
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
    return 0;
}

L

题目大意：一棵无根树，用k种颜色给节点涂色，将每种颜色的节点路径相连，得到边集，每种颜色有一个边集，求边集交的最大

思路：边集交最大，代表有更多的公共边，对于一条边来说，如果它是公共边，那么其左右必然都有大于等于k个节点，即使存在多条公共边也总能找到涂色方案使得这些公共边左右都能满足涂色大于等于k，直接找这样的边即可

代码

#include <bits/sdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+10;
int Size[maxn],T,k,head[maxn],n,cnt;
struct node {
    int from,to,next;
} e[maxn<<1];
void Add(int from,int to) {
    e[++cnt].to=to;
    e[cnt].from=from;
    e[cnt].next=head[from];
    head[from]=cnt;
}
void DFS(int u,int f) {//统计子树大小
    Size[u]=1;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(v==f)continue;
        DFS(v,u);
        Size[u]+=Size[v];
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>T;
    while(T--) {
        int res=0;
        cin >>n>>k;
        memset(head,-1,sizeof(int)*(n+1));
        memset(Size,0,sizeof(int)*(n+1));
        for(int i=1; i<n; i++) {
            int u,v;
            cin >>u>>v;
            Add(u,v);
            Add(v,u);
        }
        DFS(1,0);
        for(int i=1; i<=n; i++)
            if(Size[i]>=k&&n-Size[i]>=k)res++;
        /*这里用了一个小技巧，因为是按照序号顺序进行的，所以不会出现
        重复计算的情况，举个例子，如果1-2这条边是可行的，那么不会在
        计算1的时候计数，可以画图验证，如果有两条边都是可行的，但是
        它们共一个点，那么必然是有一个点大于公共点，一个小于公共点，
        依然可以分两次算，代码中的判断条件每次只处理了一条边
        */
        cout <<res<<endl;
    }
    return 0;
}

M

题目大意：一个n×n的地图，一些格子上有障碍不能走（少于1000个），x坐标为 [ 0 , n − 1 ] [0,n-1] [0,n−1]，y坐标为 [ 0 , n − 1 ] [0,n-1] [0,n−1]，起点在(0,0)，每次只能走相邻格，求足够长时间后终点坐标满足 x + y ≥ n − 1 x+y\ge n-1 x+y≥n−1的概率

思路：由于是足够长的时间，所以理论上除了障碍点其余点都能够到达，每个点是否能到达与能到达的概率取决于有多少个点能到它，因此，可以给每个点赋权值，权值大小表示当前点有几个点可以到达它，那么，对于一个点来说，设该点点权为 v v v，到达这个点的概率就为 v i ∑ i = 1 n v i \frac{v_i}{\sum_{i=1}^nv_i} ∑i=1n​vi​vi​​，因此，到达题目给定区域的概率就为对应面积里的点权之和除以总点权和，由于点数过多，正难则反，可以先算出总分子分母，然后减去障碍的贡献即可，注意特判

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k,Next[4][2]= {0,1,1,0,-1,0,0,-1};
map<int,bool>Umap;
int gcd(int a,int b) {
    if(b==0)return a;//注意特判b为0
    int res=1;
    while(res) {
        res=a%b;
        a=b;
        b=res;
    }
    return a;
}
void solve() {
    int mole=3*3+2*4*(n-2)+5*(n-1)*(n-2)/2;//计算分子
    int deno=3*4+4*4*(n-2)+5*(n-2)*(n-2);//
    for(auto i=Umap.begin(); i!=Umap.end(); i++) {
        if(!i->second)continue;//去掉不为障碍的点
        int y=i->first%n,x=(i->first-y)/n,val=5;//获得坐标，设定初始值
        if(x==0||x==n-1)val--;
        if(y==0||y==n-1)val--;
        deno-=val;//减去贡献
        if(x+y>=n-1)mole-=val;//同上
        for(int j=0; j<4; j++) {
            int _x=x+Next[j][0],_y=y+Next[j][1],id=_x*n+_y;//遍历邻接点
            if(_x<0||_x>n-1||_y<0||_y>n-1||Umap[id])continue;//如果越界或者是障碍
            deno--;//是格子，贡献减少
            if(_x+_y>=n-1)mole--;//是终点，贡献减少
        }
    }
    int _gcd=gcd(mole,deno);
    mole/=_gcd,deno/=_gcd;
    cout <<mole<<"/"<<deno;
    Umap.clear();
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    for(int i=1; i<=t; i++) {
        cin >>n>>k;
        cout <<"Case #"<<i<<": ";
        for(int j=1; j<=k; j++) {//标记
            int x,y;
            cin >>x>>y;
            Umap[x*n+y]=1;
        }
        if(n==1) {//特判
            if(k==1)cout <<0;
            else cout <<1;
        } else solve();
        cout <<endl;
    }
    return 0;
}

参考文献

1. HDU - 6229 Wandering Robots
2. 2017icpc沈阳 G Infinite Fraction Path BFS+剪枝