这个思路对吗?如果对的话好像不难
查看原帖
这个思路对吗?如果对的话好像不难
1437743
beta99999楼主2024/10/30 16:04

洛谷数据过了。思路是用 dp[r][v]=idp[r][v] = i 记录第 rr 轮第 ii 个人能访问到 vv 这个数。如果同一个数能被多个人访问到,则 i=1i=-1

f()f()是循环宏,rd()rd()write()write()是输入输出,不贴了。 `

const int N = 1e5 + 5, V = 2e5 + 5, L = 2e5 + 5, R = 105, INF = 1e9;
int sl[N], a[L], dp[R][V];
int main() {
    int t = rd(); while (t--) {
        int n = rd(), k = rd(), q = rd();
        f(i, 1, n) {
            sl[i] = sl[i - 1] + rd();
            f(j, sl[i - 1] + 1, sl[i]) a[j] = rd();
        }
        memset(dp, 0, sizeof dp); dp[0][1] = -1;
        f(r, 1, 100) f(i, 1, n) {
            int j0 = -INF; f(j, sl[i - 1] + 1, sl[i]) {
                int v = a[j];
                if (j - j0 < k) dp[r][v] = (dp[r][v] && dp[r][v] != i) ? -1: i;
                if (dp[r - 1][v] && dp[r - 1][v] != i) j0 = j;
            }
        }  
        while (q--) write(dp[rd()][rd()] != 0), putchar_unlocked('\n');
    }
}
2024/10/30 16:04
加载中...