头像

ycycyc

清华大学




离线:7分钟前


最近来访(182)
用户头像
码保过
用户头像
苏sov
用户头像
Snowandraw.
用户头像
码怪卢本伟
用户头像
Ruccs
用户头像
T-D-S
用户头像
SayonaraGzm
用户头像
Jacklove
用户头像
Payxtl
用户头像
Anoxia_3
用户头像
那你呢
用户头像
菜本菜
用户头像
takanasi
用户头像
Jackyc
用户头像
CYMario
用户头像
Escort
用户头像
姚军
用户头像
甘棠
用户头像
Aaaazdy
用户头像
Pipipapi


ycycyc
2天前

A

给出一个数字,例如18292,你可以选定前任意位,将它翻转,问多少次反转可以变为偶数,或者无法变为偶数即输出-1

A比较简单,如果每一位都是奇数,那调换顺序不能出现偶数,输出-1
否则如果本身就是偶数,那么不用调换,输出0
否则如果首位是偶数,那直接反转即可,输出1
否则输出2

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
int t;

signed main()
{
    cin >> t;
    while(t --)
    {
        int n; cin >> n;

        vector<int> v;
        while(n) v.pb(n % 10), n /= 10;

        bool odd = true;
        for(auto x : v)
            odd |= !(x & 1);
        if(odd) cout << -1 << endl;
        else if(v[0] % 2 == 0) cout << 0 << endl;
        else if(v.back() % 2 == 0) cout << 1 << endl;
        else cout << 2 << endl;
    }
}

B

给你两个数字,如248,200,每次要么分别取1,3,要么分别取2,2,要么分别取3,1
问最多可以取多少次

我写的是,先通过交换保证a < b
因为每次a取1,b取3的时候,差距缩小2,
并且按题目要求,只有取1,3和2,2这两种组合。
那么我分两段取,第一段取1,3让双方差距缩小到1或0
然后每次各取2人即可

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
int t;

signed main()
{
    cin >> t;
    while(t --)
    {
        int a, b;
        cin >> a >> b;
        if(a > b) swap(a, b);

        int res = min(a, (b - a) / 2);
        a -= res;
        b -= res * 3;
        res += min(a / 2, b / 2);
        cout << res << endl;
    }
}

C

给定一个排列,例如[3,1,4,2]
你需要依据它的要求进行操作
每次取端点较小值,如果它在左边,就放在新数列左边,否则放在右边
我来示范一下
[3, 1, 4, 2] []
[3, 1, 4] [2]
[1, 4] [3, 2]
[4] [1, 3, 2]
[] [4, 1, 3, 2] 或 [1, 3, 2, 4]
但题目稍微绕了一下,说它给你结果序列,问你是否存在原来的序列
例如[1, 3, 2, 4]你就可以找到原来的序列是[3, 1, 4, 2]
而[1, 3, 5, 4, 2]就找不到原来的序列了

就简单模拟一下即可,不是给了我们结果序列吗
我们每次取较大的数插回到原序列,因为越大的数肯定是越晚出来的
我们用一个双端队列实现就OK了

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin >> t;
    while(t --)
    {
        for(int i = 1; i <= 10; i ++);

        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];
        int i = 0, j = n - 1;
        deque<int> q;
        if(a[i] < a[j]) q.push_back(a[j --]);
        else q.push_back(a[i ++]);
        while(i <= j)
        {
            if(a[i] < q.back()) q.push_front(a[i ++]);
            else if(a[j] < q.front()) q.push_back(a[j --]);
            else break;
        }
        if(i > j) for(auto x : q) cout << x << ' ';
        else cout << -1;
        cout << endl;
    }
}

D

我相信每一个母语非英语的人读D都烦死了吧hhhhh
我用平板好像传不了图,不知道怎么用文字表达。。

题意是,先给一个数组,例如[3, 1, 1, 3, 1]
其实意思就是1,4号节点的双亲节点是3号节点,
2,3,5号节点的双亲节点是1号节点,于是你就可以画出一棵树了
这个数组我代码里写的是f,也就意味着f[2] = 1相当于有一条(1, 2)的边
并且如果要从2走向根节点必须往1走
又给了一个数组,例如[3, 1, 2, 5, 4]
这是个排序数组,就是3号节点的距离最小,然后是1号,然后是2号

距离指什么呢?指到根节点的距离
根节点是谁呢?第一个数组中,如果f[i] = i
也就是说自己的爸爸是自己,那它就是根节点了。。(奇怪的比喻

所以现在我们有了一棵树,以及一个排列
我看群里他们好多人用bfs,我写的不是,我写的也不知道叫啥
叫数数吧??因为就一个cnt变量贯穿始终hhh

我们明确一些东西
它要我们求什么?
要求输出一个数组,我们不是f数组中每个元素对应一条边嘛
现在要求输出每条边对应的权重
给出这样的权重组合,我们可以得到这些点与根节点的距离符合p数组的要求

OK然后就是找找规律
我画了一棵奇丑无比的大树,然后我随便找了一个点作为距离最小的点
我发现,如果不是根节点的话,这种树是不存在的,因为它还有父节点
而它的父节点离根节点一定更近。
由此又推出,如果出现排序中的任何一个点,它的父节点还未出现
意味着这个排列不合理,
因为它与根节点的距离等于它与它爹的距离加上它爹与根节点的距离啊
而如果它爹已经更新了,那么轻易可以证明,这个排列至此为止是合理的

我的做法是
1 找出根节点
2 标记所有节点为未遍历
3 按距离顺序遍历每个节点,如果这个节点不是根节点并且它爹还没出现,那这个排列错误,跳出
4 如果它爹出现了,那它就是合理的,它只要比之前出现的节点与根节点的距离都远,比之后的都近就好了
5 综上,我们让根节点意外第一个点与根节点的距离为1,第i个点的距离为i就好了
6 如何做到,我们可以立刻知道每个节点它爹的距离(因为我们确保它爹更新过了)
然后我们也知道我们想给他安排的距离是多少
题目不是问他到他爹的距离嘛
那不就是它应该有的距离减去它爹的距离
然后我们再记录一下它的距离,这样它儿子问它的时候,它也可以说出来它自己的距离啦

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5 + 10;
int f[N], p[N], w[N], d[N], st[N];
signed main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n; cin >> n;

        for(int i = 1; i <= n; i ++) cin >> f[i];
        for(int i = 1; i <= n; i ++) cin >> p[i];

        int root, cnt = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(i == f[i]) root = i;
            st[i] = 0;
        }

        bool suc = true;
        w[root] = 0;
        for(int i = 1; i <= n; i ++)
        {
            int now = p[i], pa = f[now];
            if(now != root && !st[pa])
            {
                cout << -1 << endl;
                suc = false;
                break;
            }
            st[now] = 1;
            if(now == root) d[now] = 0;
            else
            {
                w[now] = ++cnt - d[pa];
                d[now] = cnt;
            }
        }

        if(suc)
        {
            for(int i = 1; i <= n; i ++) cout << w[i] << ' ';
            cout << endl;
        }
    }
}

E1

就是一个捣蛋鬼邀请了一群捣蛋鬼来他家里玩咯
这个捣蛋鬼在1号房间,然后给你他家的地图,还告诉你其他捣蛋鬼最初在那些房间,
游戏开始,那些捣蛋鬼就要来抓主人
注意,这是个树图,没有回路
每秒钟所有人可以移动一个房间,问你这个捣蛋鬼能不能保证获胜
能则输出YES,否则输出NO
这个捣蛋鬼赢的条件是它到了终点房间,路上没有遇到别的捣蛋鬼emmm
莫名想到鱿鱼游戏

我用dfs做的
逻辑是 从1号房间出发,例如1号可以通往2,3,4号房间,我枚举这三个房间有没有一条路是活的,如果有,那么我就能活,就赢了
那么怎么判断2,3,4号房间有没有活路呢,有一个标准
首先,我到达1号房间需要走0步,对吧,那么去2,3,4号房间都需要走1步
我就看其他捣蛋鬼到2,3,4号房间的最近距离是否大于1,如果大于,那么我就是安全的,这个房间就可以到达,reach[i] = true
否则reach[i] = false
而怎么算最近捣蛋鬼距离nearest呢?
也是dfs这个房间能通往的房间,如果这个房间有鬼,那就返回0,否则就返回距离鬼最近的孩子跟鬼的距离加1(绕不绕。。
这样我就知道了哪些房间可以到达,哪些房间不可以
我再枚举所有房间,如果这个房间是终点并且可以到达,那么恭喜,赢了。
没有这样的房间,输了

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
const int N = 2e5 + 10;
vector<int> h[N];

int n, t, k, x, y, ghost[N], st[N], reach[N];

int dfs(int now, int dis)
{
    st[now] = true;
    if(ghost[now]) return 0;
    int nearest = N;
    for(auto x : h[now])
        if(!st[x])
            nearest = min(nearest, dfs(x, dis + 1));
    if(nearest + 1 > dis) reach[now] = true;
    // cout << now << ' ' << reach[now] << ' ' << dis << ' ' << nearest << endl;
    return nearest + 1;
}

bool dfs2(int now)
{
    if(h[now].size() == 1 && now != 1) return true;
    reach[now] = false;
    for(auto & x : h[now]) if(reach[x] && dfs2(x)) return true;
    return false;
}

signed main()
{
    cin >> t;
    while(t --)
    {
        cin >> n >> k;

        for(int i = 1; i <= n; i ++)
        {
            h[i].clear();
            reach[i] = st[i] = ghost[i] = 0;
        }
        for(int i = 1; i <= k; i ++)
        {
            cin >> x;
            ghost[x] = 1;
        }
        for(int i = 1; i < n; i ++)
        {
            cin >> x >> y;
            h[x].pb(y);
            h[y].pb(x);
        }

        dfs(1, 0);

        // for(int i = 1; i <= n; i ++) cout << reach[i] << ' ';
        // cout << endl;
        if(dfs2(1)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

E2

E2其实与E1改动不多,问的是坏孩子的角度,就是被邀请的捣蛋鬼朋友的角度
问题是留下多少捣蛋鬼可以把主人抓住,如果无论如何都抓不住,那就输出-1,否则输出留下的捣蛋鬼的个数,你看,它没有要求你说留下哪些捣蛋鬼,一下子就变得很容易

仍然是dfs,我的dfs思路是,先按原来的得到每个房间是否可以到达
题目转化为,要把1号房间的所有出路堵死需要留下多少人
还是例如1号可以去2,3,4号
假如我们发现2号去不了,那也就是说如果走2号,会有坏人在你之前到达2号,所以2号这条路通往的子树里面留一个捣蛋鬼就够了,对,就留那个可以最快速度来到这个位置的
所以num ++;
而如果走3号,你发现3号是可到达的,那你就去看把三号房间的所有出路堵死需要留下多少人,那就是dfs(3)人嘛
所以输出dfs(1)即可,当然,同时需要判断有没有堵不死的情况,over

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
const int N = 2e5 + 10;
vector<int> h[N];

int n, t, k, x, y, suc, ghost[N], st[N], reach[N];

int dfs(int now, int dis)
{
    st[now] = true;
    if(ghost[now]) return 0;
    int nearest = N;
    for(auto x : h[now])
        if(!st[x])
            nearest = min(nearest, dfs(x, dis + 1));
    if(nearest + 1 > dis) reach[now] = true;
    return nearest + 1;
}

int dfs2(int now)
{
    if(now != 1 && h[now].size() == 1)
        suc = false;

    st[now] = true;
    int num = 0;
    reach[now] = false;
    for(auto x : h[now])
    {
        if(st[x]) continue;
        if(reach[x]) num += dfs2(x);
        else num ++;
    }
    return num;
}

signed main()
{
    cin >> t;
    while(t --)
    {
        cin >> n >> k;

        for(int i = 1; i <= n; i ++)
        {
            h[i].clear();
            reach[i] = st[i] = ghost[i] = 0;
        }
        for(int i = 1; i <= k; i ++)
        {
            cin >> x;
            ghost[x] = 1;
        }
        for(int i = 1; i < n; i ++)
        {
            cin >> x >> y;
            h[x].pb(y);
            h[y].pb(x);
        }

        dfs(1, 0);

        suc = true;
        for(int i = 1; i <= n; i ++) st[i] = false;
        int res = dfs2(1);

        if(suc) cout << res << endl;
        else cout << -1 << endl;
    }
}

F

F就很简单了,双指针嘛
问题是,小朋友开了一家银行,有很多人来存钱取钱,给你一个序列,比如
[-16, 2, -6, 8],并且告诉你小朋友最开始有10块钱
他很坏,他可以不那么早开门,第一个人取16块,他给不起,他就等他走了再开门
假如他在时间为1的时候开门,那他可以服务的客人是0嘛,但是如果在2时刻开门
他可以先服务第一个人,存了2块,他就有12块了,服务第二个人,取了6块,他还有6块,服务第三个人,存了8块,他又有14块了
问你,他想要服务最多的人,可以什么时候开门,什么时候关门
注意他只能开关门一次
不知道这个是不是叫滑动窗口来着

这个问题有一定单调性
比如这个数列的最优解是2,4,
如果2开门,4关门可以满足的话,意味着2,3一定可以满足,2,2,也一定可以满足
所以当我们左端点固定时,虽说要枚举右端点,但是有单调性,一直往右就行
如果2,4满足,第5个人要取100000块,那么就不行了,我们就只能从左边缩
意思是如果2,5不可以,那么2,6一定不可以,但是3,5可能可以
如果3,5不可以,3,6肯定不可以,但是4,5可能可以
如果还是不行,那看看5,5
还不行,那左端点再移动,就把这个5排出去了,就相当于看看6以后的情况了
其实想想也很合理,你取那么多钱,我这个点我不开了,诶,就是玩儿

所以我们将枚举所有左右端点的$(O(n*n))$的复杂度缩减到了线性的$O(n)$
(20w个点,你暴力肯定过不去的)
注意,题目想问最多的连续,那么它会在什么时候出现?当然是右端点扩张的时候可能更新最大值,左端点萎缩的时候是不可能更新记录的

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5 + 10;
int a[N];
signed main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int l = 1, r = 1;
        int resl, resr, M = 0;

        int n, s; cin >> n >> s;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        while(r <= n)
        {
            if(s + a[r] >= 0)
            {
                s += a[r ++];
                if(r - l > M)
                {
                    M = r - l;
                    resr = r - 1;
                    resl = l;
                }
            }
            else if(l == r) l ++, r ++;
            else s -= a[l ++];
        }

        if(M) cout << resl << ' ' << resr << endl;
        else cout << -1 << endl;
    }
}

G

G比赛没写出来,现在也懒得写了2333,反正也许大概应该是二分吧,下班!




ycycyc
1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int ne[N];

int n, m;
string s, p;

int main()
{
    cin >> m >> p >> n >> s;

    int i = 0, j = -1;
    ne[0] = -1;

    while(i < m)
    {
        if(j == -1 || p[i] == p[j]) ne[++ i] = ++ j;
        else j = ne[j];
    }

    i = 0, j = 0;
    while(i < n)
    {
        if(j == -1 || p[j] == s[i]) i ++, j ++;
        else j = ne[j];
        if(j == m) cout << i - j << ' ', j = ne[j];
    }
}



ycycyc
1个月前

通畅~

#include<bits/stdc++.h>

using namespace std;

int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

int main()
{
    int n;
    cin >> n;

    int g[n][n] = {0};
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> g[i][j];

    queue<pair<int, int>> q;
    q.push({0, 0});

    bool st[n][n] = {false};
    st[0][0] = true;

    pair<int, int> path[n][n];
    path[0][0] = {-1, -1};

    while(q.size())
    {
        auto [x, y] = q.front();
        q.pop();

        if(x == n - 1 && y == n - 1)
        {
            vector<pair<int, int>> res;

            auto [a, b] = path[x][y];
            while(x != -1)
            {
                res.push_back({x, y});
                x = a, y = b;
                a = path[x][y].first;
                b = path[x][y].second;
            }

            reverse(res.begin(), res.end());

            for(auto x : res) cout << x.first << ' ' << x.second << endl;
            return 0;
        }

        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(st[a][b] || g[a][b]) continue;

            path[a][b] = {x, y};
            st[a][b] = true;
            q.push({a, b});
        }
    }
}



ycycyc
1个月前

A

因为都 >= 1
c实际上只有奇数和偶数,消掉也就是0和1
如果c是1,那么与一个b结合差值就成了1
把剩下的b与a结合即可
所以b不影响,只有a和c会影响结果是1或0

#include<bits/stdc++.h>

using namespace std;

// A 500分题

int main()
{
    int t;
    cin >> t;

    while(t --)
    {
        int a, b, c;
        cin >> a >> b >> c;

        cout << ((a + c) & 1) << endl;
    }
}

B

统计0和1的数量
必须取1个1
每个0都可取可不取,也就是有2种选择,所以每个0乘2

#include<bits/stdc++.h>

using namespace std;

// B 750分题

#define int long long

signed main()
{
    int t;
    cin >> t;

    while(t --)
    {
        int n, n0 = 0, n1 = 0;
        cin >> n;

        for(int i = 0; i < n; i ++)
        {
            int x;
            cin >> x;

            if(x == 0) n0 ++;
            if(x == 1) n1 ++;
        }

        cout << n1 * (1ll << n0) << endl;
    }
}

C

#include<bits/stdc++.h>

using namespace std;

// C 1500分题

int main()
{
    int t;
    cin >> t;

    while(t --)
    {
        int n;
        cin >> n;

        string s;
        cin >> s;

        int res = -1;

        for(int i = 0; i < 26; i ++) // 枚举a—z
        {
            int l = 0, r = n - 1, cnt = 0;
            while(l < r)
            {
                if(s[l] == s[r]) l ++, r --; // 对称
                else if(s[l] - 'a' == i) l ++, cnt ++; // 不对称但是可以删
                else if(s[r] - 'a' == i) r --, cnt ++; // +1
                else break;
            }

            // 删除后l左边和r右边是对称的
            if(l >= r) // 删除后成功回文了
            {
                if(res == -1) res = cnt;
                else res = min(res, cnt);
            }
        }

        cout << res << endl;
    }
}

D

如果有偶数个,两两相消即可。
如果有奇数个,我们让除了前三个以外的偶数个两两相消
前三个我们要保证没有0出现,所以我选择枚举三种一消二的可能

#include<bits/stdc++.h>

using namespace std;

// D 1750分题

int main()
{
    int t;
    cin >> t;

    while(t --)
    {
        int n;
        cin >> n;

        vector<int> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];

        if(n & 1)
        {
            if (a[1] + a[2])
                cout << a[1] + a[2] << ' ' << -a[0] << ' ' << -a[0] << ' ';
            else if(a[0] + a[2])
                cout << -a[1] << ' ' << a[0] + a[2] << ' ' << -a[1] << ' ';
            else if(a[0] + a[1])
                cout << -a[2] << ' ' << -a[2] << ' ' << a[0] + a[1] << ' ';
            for(int i = 3; i < n; i += 2)
                cout << a[i + 1] << ' ' << -a[i] << ' ';
        }
        else
        {
            for(int i = 0; i < n; i += 2)
                cout << a[i + 1] << ' ' << -a[i] << ' ';
        }

        cout << endl;
    }
}



ycycyc
1个月前

A

首先筛质数,方便后面直接判断某个数是否为合数。
如果几个数的和为合数,则直接输出
如果为质数,那么一定为奇数,那么这几个数中一定有奇数,减掉这个数后即为合数
也就是说答案要么为n,要么为n-1,我就写了个判断,然后按需输出即可。

#include<bits/stdc++.h>

using namespace std;

bool prim[20020];

int main()
{
    int t; cin >> t;

    for(int i = 2; i <= 2e4; i ++) prim[i] = true;
    for(int i = 2; i <= 2e4; i ++)
        if(prim[i])
            for(int j = i << 1; j <= 2e4; j += i) prim[j] = false;

    while(t --)
    {
        int n, tot = 0; cin >> n;

        vector<int> a(n);
        for(auto & x : a) cin >> x, tot += x;

        if(!prim[tot])
        {
            cout << n << endl;
            for(int i = 1; i <= n; i ++) cout << i << ' ';
            cout << endl;
        }
        else
        {
            for(int i = 0; i < n; i ++)
                if(!prim[tot - a[i]])
                {
                    cout << n - 1 << endl;
                    for(int j = 0; j < n; j ++)
                        if(i != j) cout << j + 1 << ' ';
                    cout << endl;
                    break;
                }
        }
    }
}

B

菊花图精辟。
如果我们画一个菊花,也就是所有点和同一个点相连,那么遍历任意三个外围的点的路径就是:外围,中心,外围,中心,外围。如果把中心放在起点或者终点也需要走重复的路径。
所以我看了一下数据范围,m<n,那么一定有个点没有在b的位置出现过,把它作为中心一定满足所有条件。

#include<bits/stdc++.h>

using namespace std;

bool prim[20020];

int main()
{
    int t; cin >> t;

    while(t --)
    {
        int n, m; cin >> n >> m;

        int a, b, c;
        bool st[n] = {false};

        for(int i = 1; i <= m; i ++)
            cin >> a >> b >> c, st[--b] = true;

        for(int i = 0; i < n; i ++)
            if(!st[i])
            {
                for(int j = 0; j < n; j ++)
                    if(i != j) cout << i + 1 << ' ' << j + 1 << endl;
                break;
            }
    }
}

C

题意是,先告诉你.X图,你可以就此推出EN图,问你据此EN图能否唯一确定.X图。
思路是如果存在

? X
X ?

的情况,得出来的EN图就是

? N
N N

左上角的?不影响,右下角的?无论是’.’还是’X’,都得到N,那么这个EN图就不能回去唯一确定.X图,所以就要输出NO
代码就统计一下每个位置会不会有这样斜的X,然后用前缀和优化或者把bad_position放vector里面用lower_bound什么的都行

#include<bits/stdc++.h>

using namespace std;

bool prim[20020];

int main()
{
    int n, m; cin >> n >> m;

    char g[n][m];
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> g[i][j];

    int un[m + 1] = {0};
    for(int i = 1; i < n; i ++)
        for(int j = 0; j < m - 1; j ++)
            if(g[i][j] == 'X' && g[i - 1][j + 1] == 'X')
                un[j + 1] ++;
    for(int j = 1; j <= m; j ++) un[j] += un[j - 1];

    int q, l, r; cin >> q;
    while(q --)
    {
        cin >> l >> r;
        cout << (un[r - 1] == un[l - 1] ? "YES\n" : "NO\n");
    }
}

D

permutation的特点在于各个数都不相同,所以如果所有数同时+1,那么结果也各不相同。
我们以最后一个数为基准,让它+1,以此让前面所有数统一+1~n,举个例子,最后一个数+1,前面的数都+5,结果是3,那就是第3个数比最后一个数大(1-5)也就是小4.这样我们可以得到1到n-1里所有比最后一个数小的数的下标和差值,同理让最后一个数+n再来一次也可以得到前面所有比它大的数的下标和差值,综合到一起得到整个排列。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n; cin >> n;

    int num[n + 1] = {0};
    for(int i : {1, n})
        for(int j = 1; j <= n; j ++)
        {
            cout << '?' << ' ';
            for(int k = 1; k < n; k ++) cout << j << ' ';
            cout << i << endl;

            int seq; cin >> seq;
            num[seq] = i - j;
        }

    int M = 0;
    for(int i = 1; i <= n; i ++) M = max(M, num[i]);
    for(int i = 1; i <= n; i ++) num[i] = n - M + num[i];

    cout << '!' << ' ';
    for(int i = 1; i <= n; i ++) cout << num[i] << ' ';
}

E

如果所有点被问偶数次,那么就是YES,因为我们可以构造一个树,让每次访问它都沿着这条树走。
如果有点被问奇数次,那么就是NO,因为与它相连的路径总和是奇数,就一定有一条路总和是奇数。
把两种情况综合到一起就是代码。

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long
const int N = 3e5 + 10;
vector<int> h[N];
int p[N], st[N], qu[N], qv[N], t[N], d[N];

void dfs(int u)
{
    st[u] = true;
    for(auto x : h[u])
        if(!st[x]) p[x] = u, d[x] = d[u] + 1, dfs(x);
}

signed main()
{
    int n, m; cin >> n >> m;

    int x, y;
    for(int i = 1; i <= m; i ++)
        cin >> x >> y, h[x].pb(y), h[y].pb(x);

    d[1] = 1; dfs(1);

    int res = 0, q; cin >> q;
    for(int i = 1; i <= q; i ++) cin >> qu[i] >> qv[i], t[qu[i]] ++, t[qv[i]] ++;
    for(int i = 1; i <= n; i ++) res += t[i] & 1;

    if(res) cout << "NO\n" << res / 2;
    else
    {
        cout << "YES";
        for(int i = 1; i <= q; i ++)
        {
            x = qu[i], y = qv[i];
            vector<int> out1, out2;

            while(x != y)
                if(d[x] > d[y]) out1.pb(x), x = p[x];
                else out2.pb(y), y = p[y];
            out1.pb(x);

            reverse(out2.begin(), out2.end());
            cout << endl << out1.size() + out2.size() << endl;

            for(auto out : out1) cout << out << ' ';
            for(auto out : out2) cout << out << ' ';
        }
    }
}



ycycyc
1个月前

$gcd(a, m) = gcd(a+x, m) = d$
–>( a % d ) = ( m % d ) = ( ( a + x ) % d ) = 0
–>gcd($(a + x) / d$ , $ m / d $) = 1
我们统计有多少满足条件的x
如果是暴力,那就是

for(int i = a; i < a + m; i += d)
    if(__gcd(i, m) == 1) res ++;

但是统计互质的数的数量复杂度太大需要改进
我们在幼儿园学过求一个数的质因数有哪些,这个复杂度只在$O(sqrt(N))$

我们首先令$res = n$,这是总数。
然后我们开始做减法,我们看看$(a , a + m - 1)$这个区间里面有多少数与$m/d$不互质

例如100有质因数2,5那么100里面有多少数与2不互质呢?
对,100/2,那么有多少和5不互质呢?
对,100/5。你甚至知道每100个数都有20个数与100不互质。

至此我们得到一个结论,就是区间$(a / d , (a + m - 1) / d)$内与2不互质的数与区间$(0, m)$内的数量完全一致,那么我们只需要求$(0, m / d)$区间就行了。
不是因为从0开始好看,而是因为好求。

我们只需要求m / d的质因数a,然后把res个数中(res / a)个数减去即可。

我们可以这样写

#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main()
{
    int t, a, b;
    cin >> t;

    while(t --)
    {
        cin >> a >> b;
        int d = __gcd(a, b);
        b /= d;
        int res = b;

        vector<int> v;
        for(int i = 2; i <= b / i; i ++)
            if(b % i) continue;
            else
            {
                while(!(b % i)) b /= i;
                v.push_back(i);
            }

        if(b - 1) v.push_back(b);
        for(auto x : v) res -= res / x;

        cout << res << endl;
    }
}

也可以合并到一起,不用vector去存

#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main()
{
    int t, a, b;
    cin >> t;

    while(t --)
    {
        cin >> a >> b;
        int d = __gcd(a, b);
        b /= d;
        int res = b;

        for(int i = 2; i <= b / i; i ++)
            if(b % i) continue;
            else
            {
                while(!(b % i)) b /= i;
                (res /= i) *= (i - 1);
            }

        if(b > 1) (res /= b) *= (b - 1);

        cout << res << endl;
    }
}


活动打卡代码 AcWing 3999. 最大公约数

ycycyc
1个月前

$gcd(a, m) = gcd(a+x, m) = d$
–>( a % d ) = ( m % d ) = ( ( a + x ) % d ) = 0
–>gcd($(a + x) / d$ , $ m / d $) = 1
我们统计有多少满足条件的x
如果是暴力,那就是

for(int i = a; i < a + m; i += d)
    if(__gcd(i, m) == 1) res ++;

但是统计互质的数的数量复杂度太大需要改进
我们在幼儿园学过求一个数的质因数有哪些,这个复杂度只在$O(sqrt(N))$

我们首先令$res = n$,这是总数。
然后我们开始做减法,我们看看$(a , a + m - 1)$这个区间里面有多少数与$m/d$不互质

例如100有质因数2,5那么100里面有多少数与2不互质呢?
对,100/2,那么有多少和5不互质呢?
对,100/5。你甚至知道每100个数都有20个数与100不互质。

至此我们得到一个结论,就是区间$(a / d , (a + m - 1) / d)$内与2不互质的数与区间$(0, m)$内的数量完全一致,那么我们只需要求$(0, m / d)$区间就行了。
不是因为从0开始好看,而是因为好求。

我们只需要求m / d的质因数a,然后把res个数中(res / a)个数减去即可。

#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main()
{
    int t, a, b;
    cin >> t;

    while(t --)
    {
        cin >> a >> b;
        int d = __gcd(a, b);
        b /= d;
        int res = b;

        for(int i = 2; i <= b / i; i ++)
            if(b % i) continue;
            else
            {
                while(!(b % i)) b /= i;
                (res /= i) *= (i - 1);
            }

        if(b > 1) (res /= b) *= (b - 1);

        cout << res << endl;
    }
}



ycycyc
1个月前

A

给出三个人分别的得票数,单独问每个人如果要赢还需要多少票。
三种情况 小中大,小小大,小大大,分类讨论一下即可。
我的做法稍微归纳了一下,显得没那么复杂。。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t, a[3], b[3];
    cin >> t;
    while(t --)
    {
        int M = 0, cnt = 0;

        for(int i = 0; i < 3; i ++) cin >> a[i], M = max(M, a[i]);
        for(int i = 0; i < 3; i ++) if((b[i] = M - a[i] + 1) == 1) cnt ++;
        if(cnt == 1) for(int i = 0; i < 3; i ++) if(b[i] == 1) b[i] --;

        for(auto x : b) cout << x << ' ';
        cout << endl;
    }
}

B

手动模拟一下,从个位开始数,看看数到第几位的时候满足出现50或者00或者25或者75
其实可以只写一次循环,可是复制粘贴何乐而不为23333

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> v;
        while(n) v.push_back(n % 10), n /= 10;//把每一位拎出来

        int i = 0, s = 0, vn = v.size(), res;
        while(i < vn) 
            if(!s)
            {
                if(v[i ++] == 0) s = 1;
            }
            else
            {
                if(v[i] == 5 || v[i] == 0) break;
                i ++;
            }
        res = i; s = 0; i = 0;
        while(i < vn) 
            if(!s)
            {
                if(v[i ++] == 5) s = 1;
            }
            else
            {
                if(v[i] == 7 || v[i] == 2) break;
                i ++;
            }
        res = min(i, res);

        cout << res - 1 << endl;
    }
}

C

贪心,越接近hole的越先走。
主要两个公式说明一下

if(n > x.f * x.s) res += x.s, n -= x.f * x.s;
res += (n - 1) / x.f;

思路都是,猫来到这个格子之前,能走的走了,没走的死了。
第一个公式是,猫还远呢,这个格子可以全走光
第二个共识是,猫近了,猫到这个格子的距离$(n-x.f)/(x.f)$向上取整
所以$(n-x.f+x.f-1)/(x.f)$

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

signed main()
{
    int t, n, k, x;
    cin >> t;
    while(t --)
    {
        cin >> n >> k;
        map<int, int> p;
        for(int i = 0; i < k; i ++) cin >> x, p[n - x] ++;

        int res = 0;
        for(auto x : p)
            if(n > x.f * x.s) res += x.s, n -= x.f * x.s;
            else
            {
                res += (n - 1) / x.f;
                break;
            }

        cout << res << endl;
    }
}

D1

D1就是枚举这些数两两之间差值的gcd,我排序一下可以优化到$O(nlogn)$,不过没啥必要
1 gcd是什么 gcd:最小公因数
2 为什么是gcd:例如1 3 5他们的差值有2和4,如果我们取4,可以让1和5相同,但取gcd2可以让1 3 5都相同,因为它们之间的差值都是gcd2的倍数,一定可以通过加减若干个2变成相同的数。

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

signed main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];
        sort(a.begin(), a.end());

        if(a[0] == a[n - 1]) cout << -1 << endl;
        else 
        {
            int res = a[1] - a[0];
            for(int i = 1; i < n; i ++) res = __gcd(res, a[i] - a[i - 1]);
            cout << res << endl;
        }
    }
}

D2

D2我看数据量很小就暴力了
首先判断一下是否存在超过n/2个相同元素,存在则输出-1
否则,求出两两之间的差值,再求出差值间两两gcd,枚举每个gcd看能不能达到让n/2个数相同,也就是枚举每个数,看看有没有n/2个数和它的差值是这个gcd的倍数
(现在想想好像可以构造数据T掉啊,现在还可以hack,大家想到了的话快冲)

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

signed main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];

        int res = 0;
        map<int, int> cnt;
        for(int i = 0; i < n; i ++) cnt[a[i]] ++;
        for(auto x : cnt) if(x.s >= n / 2) res = -1;

        if(!res)
        {
            set<int> gcds, d;
            for(auto x : a) for(auto y : a) d.insert(abs(x - y));
            for(auto x : d)
                for(auto y : d)
                    gcds.insert(__gcd(x, y));

            for(auto x : gcds)
            {
                if(!x) continue;
                for(int i = 0; i < n; i ++)
                {
                    int c = 0;
                    for(int j = 0; j < n; j ++)
                        if(abs(a[i] - a[j]) % x == 0) c ++;
                    if(c >= n / 2) res = max(res, x);
                }
            }
        }

        cout << res << endl;
    }
}

E

如果只有1个点,那一定会被消掉
如果大于1个点,那就是拓扑排序,每次把度为1的节点去掉,并且把与之相连的节点度-1

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
using namespace std;

signed main()
{
    int t, n, k, x, y;
    cin >> t;
    while(t --)
    {
        cin >> n >> k;
        if(n == 1)
        {
            cout << 0 << endl;
            continue;
        }

        vector<int> h[n], vs;
        for(int i = 1; i < n; i ++) cin >> x >> y, h[--x].pb(--y), h[y].pb(x);
        int d[n];
        for(int i = 0; i < n; i ++) if((d[i] = h[i].size()) == 1) vs.pb(i);

        int res = n;
        while(k --)
        {
            if(!vs.size()) break;
            res -= vs.size();
            vector<int> backup;
            for(auto x : vs) backup.pb(x);
            vs.clear();

            for(auto u : backup)
                for(auto v : h[u]) if(--d[v] == 1) vs.pb(v);
        }

        cout << res << endl;
    }
}

F

dp,因为状态是有限的,然后注意$((a * 10 + b) % c = (a % c) * (10 % c) + b % c)$

#include<bits/stdc++.h>

using namespace std;

int t, n, a, b;
int dp[41][41][40][40], num[50];

struct state{
    int pos, n, rn, bn;
    char s[40];
};

struct
{
    int d;
    char s[40];
} res;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    while(t --)
    {
        cin >> n >> a >> b;
        string s;
        cin >> s;

        for(int i = 1; i <= n; i ++) num[i] = s[i - 1] - '0';
        queue<struct state> q;
        // struct state begin = 
        q.push({0, 0, 0, 0, {'R'}});

        memset(dp, 0, sizeof dp);
        dp[0][0][0][0] = 1;
        res = {0x3f3f3f3f, {'R'}};

        while(q.size())
        {
            auto x = q.front();
            q.pop();

            // cout << x.pos << ' ' << x.n << ' ' << x.rn << ' ' << x.bn << ' ' << x.s << endl;

            if(x.pos == n)
            {
                if(abs(2 * x.n - n) < res.d && !x.rn && !x.bn && x.n && x.n < n)
                {
                    res.d = abs(2 * x.n - n);
                    for(int i = 0; i < n; i ++) res.s[i] = x.s[i];
                }
                continue;
            }

            auto y = x;
            x.n ++;
            x.rn = (x.rn * 10 + num[x.pos + 1]) % a;
            x.s[x.pos ++] = 'R';
            if(!dp[x.pos][x.n][x.rn][x.bn])
                dp[x.pos][x.n][x.rn][x.bn] = 1,
                q.push(x);

            y.bn = (y.bn * 10 + num[y.pos + 1]) % b;
            y.s[y.pos ++] = 'B';
            if(!dp[y.pos][y.n][y.rn][y.bn])
                dp[y.pos][y.n][y.rn][y.bn] = 1,
                q.push(y);
        }

        if(res.d == 0x3f3f3f3f) cout << -1 << endl;
        else cout << res.s << endl;
    }
}

G

方法一
线段树,枚举各种情况,pushup的时候注意,每个线段只保留010101或者10101序列
也就是说00和11会被消掉,这里的1表示小括号,0表示中括号。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

string s;
char str[N];

struct segtr
{
    int l, r;
    int xiao, num;
} tr[4 * N];

void pushup(segtr & u, segtr l, segtr r)
{
    if(!l.num) 
        u = {l.l, r.r, r.xiao, r.num};
    else if(!r.num)
        u = {l.l, r.r, l.xiao, l.num};
    else if(l.xiao == r.xiao && !(l.num & 1) || l.xiao != r.xiao && l.num & 1)
        u = {l.l, r.r, l.xiao, l.num + r.num};
    else if(l.num >= r.num) 
        u = {l.l, r.r, l.xiao, l.num - r.num};
    else if(r.xiao && !(l.num & 1) || !r.xiao && l.num & 1) 
        u = {l.l, r.r, 1, r.num - l.num};
    else 
        u = {l.l, r.r, 0, r.num - l.num};
}

void pushup(int u, int l, int r)
{
    pushup(tr[u], tr[l], tr[r]);
}

void build(int u, int l, int r)
{
    if(l >= r)
    {
        if(str[l] == '(') tr[u] = {l, r, 1, 1};
        else tr[u] = {l, r, 0, 1};
        return;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u, u << 1, u << 1 | 1);
}

segtr query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r) return tr[u];

    int mid = tr[u].l + tr[u].r >> 1;
    if(l > mid) return query(u << 1 | 1, l, r);
    if(r <= mid) return query(u << 1, l, r);

    segtr res, lchild = query(u << 1, l, mid), rchild = query(u << 1 | 1, mid + 1, r);
    pushup(res, lchild, rchild);
    return res;
}

int main()
{
    int t, q, n;
    cin >> t;

    while(t --)
    {
        cin >> s >> q;
        n = s.size();

        for(int i = 0; i < n; i ++)
            if(s[i] == '(' || s[i] == ')') str[i + 1] = '(';
            else str[i + 1] = '[';

        build(1, 1, n);

        while(q --)
        {
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r).num / 2 << endl;
        }
    }
}

方法二
前缀和,注意奇数位置的中括号只能和偶数位置的中括号消掉,我们看看有多少没有消掉的括号,那么代价就是多少。
统计一下,奇数位加一,偶数位减一即可,我是这样写的(因为懒得写判断

sum[i + 1] = sum[i] + (i & 1) * 2 - 1;

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int t, q, sum[N];
string s;

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> s;
        int n = s.size();

        for(int i = 0; i < n; i ++)
            if(s[i] == '(' || s[i] == ')') sum[i + 1] = sum[i];
            else sum[i + 1] = sum[i] + (i & 1) * 2 - 1;

        cin >> q;
        while(q --)
        {
            int l, r;
            cin >> l >> r;
            cout << abs(sum[r] - sum[l - 1]) << endl;
        }
    }
}



ycycyc
1个月前

这次比赛怎么追都追不上,然后发现泄题了,好离谱啊!


A

模拟即可

#include<bits/stdc++.h>

using namespace std;

int n;

bool solve()
{
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    for(int i = 0; i < n; i ++) if(s1[i] + s2[i] == '1' + '1') return false;
    return true;
}

int main()
{
    int T;
    cin >> T;
    while(T --) if(solve()) cout << "YES\n"; else cout << "NO\n";
}

B

暴力
用cnt1,cnt2两个数组去记录,然后枚举各种可能结果,(1,2),(1,3)这样
成功的等价条件是,存在

if(j != i && cnt2[j] + min(cnt1[j], cnt1[i] - n / 2) >= n / 2)

解释一下就是首先i和j不能相同,举个例子,含有1的有5组,其中有2组含有2,不含有1但是含有2的有3组,一共8组,那我就可以从含有1的5组中拿出1组给2,然后就有4组含有1,和4组含有2,需要判断的是,我可以从1中拿出多少组呢,首先要保证我有那么多2,其次要保证拿出来之后,我剩下的1还够用,我至少要剩下n/2个1的!

#include<bits/stdc++.h>

using namespace std;

int n;

bool solve()
{
    cin >> n;
    vector<vector<int>> a(n);

    for(int i = 0; i < n; i ++)
    {
        a[i] = vector<int> (5, 0);
        for(int j = 0; j < 5; j ++) cin >> a[i][j];
    }

    for(int i = 0; i < 5; i ++)
    {
        int cnt1[5] = {0}, cnt2[5] = {0};

        for(int j = 0; j < n; j ++)
            if(a[j][i])
                for(int k = 0; k < 5; k ++) cnt1[k] += a[j][k];
            else for(int k = 0; k < 5; k ++) cnt2[k] += a[j][k];

        if(cnt1[i] < n / 2) continue;

        for(int j = 0; j < 5; j ++)
            if(j != i && cnt2[j] + min(cnt1[j], cnt1[i] - n / 2) >= n / 2)         return true;

    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while(T --) if(solve()) cout << "YES\n"; else cout << "NO\n";
}

C

C题写了long double,然后觉得精度不够,灵机一动写long long2333
a和b可以一起消掉等价于(a + b) / 2 * n = total
用个map去存方便找数就过了

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve()
{
    ll s = 0, n, res = 0;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i ++) cin >> a[i], s += a[i];

    if(!(s * 2 % n))
    {
        map<ll, ll> cnt;
        for(auto x : a) cnt[x] ++;

        for(auto x : cnt)
            if(x.first * n == s) res += x.second * (x.second - 1);
            else if(cnt.count(s * 2 / n - x.first)) 
                res += x.second * cnt[s * 2 / n - x.first];
    }

    cout << res / 2 << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T --) solve();
}

D

就是组合问题,首先算C(n,3),然后减掉不合理的部分
首先我们知道不会出现两个(a, b),即a相同时b一定不同,反过来也是

所以如果一个组中三个a相同,那它合理,如果三个a各不相同,那也合理
不合理的只有一种就是(a, b), (a, c), ((d, b)或(d, c))

所以我们统计一下两个数组各个数各有多少,然后我们遍历从1到n
包含(a, b) 的有(v1中a的个数-1)*(v2中b的个数-1)个,累加即可

我用an数组因为他有说ai<=n,不然就用map也可以,应该不会T
有趣的是,这道题泄题的答案里面没有整成ll,然后出现大量抄题解然后被hack的情况,所以大家可以上号看看排名又前进了多少2333

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve()
{
    ll res = 0, n;
    cin >> n;
    vector<ll> a(n), b(n), an(n), bn(n);
    for(int i = 0; i < n; i ++) cin >> a[i] >> b[i], an[--a[i]] ++, bn[--b[i]] ++;
    res = n * (n - 1) * (n - 2) / 6;
    for(int i = 0; i < n; i ++) res -= (an[a[i]] - 1ll) * (bn[b[i]] - 1ll);
    cout << res << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T --) solve();
}

E

E我的做法也是模拟,虽然整个图是1000*1000,但是我想了想,每次只改变一个块的话,我只搜索看看我这个块lock上和unlock的时候对结果的影响,如果unlock就加上,lock就减去,时间复杂度倒也不高,因为是模拟,所以代码写的就很长,凑合看hhh

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1117;
ll tot = 0, n, m, g[N][N], q;

void update()
{
    int x, y;
    cin >> x >> y;
    int r1 = 1, r2 = 1, c1 = 1, c2 = 1;

    for(int i = 1; ; i ++) 
        if(x + i <= n && y + i - 1 <= m && !g[x + i][y + i - 1])
        {
            r1 ++;
            if(y + i <= m && !g[x + i][y + i]) r1 ++;
            else break;
        } else break;

    for(int i = 1; ; i ++) 
        if(y - i && x - i + 1 && !g[x - i + 1][y - i])
        {
            r2 ++;
            if(x - i && !g[x - i][y - i]) r2 ++;
            else break;
        } else break;

    for(int i = 1; ; i ++)
        if(x + i - 1 <= n && y + i <= m && !g[x + i - 1][y + i])
        {
            c1 ++;
            if(x + i <= n && !g[x + i][y + i]) c1 ++;
            else break;
        } else break;

    for(int i = 1; ; i ++)
        if(x - i && y - i + 1 && !g[x - i][y - i + 1])
        {
            c2 ++;
            if(y - i && !g[x - i][y - i]) c2 ++;
            else break;
        } else break;

    if(g[x][y]) g[x][y] = 0, tot += 1ll * r1 * r2 + 1ll * c1 * c2 - 1;
    else g[x][y] = 1, tot -= 1ll * r1 * r2 + 1ll * c1 * c2 - 1;

    cout << tot << endl;
}

void solve()
{
    cin >> n >> m >> q;

    tot = n * m;
    for(int i = 2; i <= min(m, n) + 1; i ++) 
        tot += (m - i + 1) * (n - i + 2) + (n - i + 1) * (m - i + 2)
            + (m - i + 1) * (n - i + 1) * 2;

    while(q --) update();
}

int main()
{
    int T;
    T = 1;
    while(T --) solve();
}


活动打卡代码 AcWing 854. Floyd求最短路

ycycyc
1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 300;
int d[N][N], n, m, k, x, y, z;

int main()
{
    cin >> n >> m >> k;

    memset(d, 0x3f3f3f3f, sizeof d);
    for(int i = 1; i <= n; i ++) d[i][i] = 0;
    for(int i = 1; i <= m; i ++) cin >> x >> y >> z, d[x][y] = min(d[x][y], z);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            for(int u = 1; u <= n; u ++)
                d[j][u] = min(d[j][u], d[j][i] + d[i][u]);
    for(int i = 1; i <= k; i ++) cin >> x >> y, 
        d[x][y] >= 0x3f3f3f3f / 2 ? cout << "impossible\n" : cout << d[x][y] << endl;
}