2 条题解

  • 2
    @ 2023-11-1 20:18:42
    #include <cstdio>
    
    const int N = 2.5e6 + 20, M = 2e4 + 7;
    
    int n, m;
    char c;
    
    void in(int &x)
    {
    	c = getchar();
    	while(c > '9' || c < '0') c = getchar();
    	for(x = 0; c >= '0' && c <= '9'; c = getchar())
    		x = x * 10 + c - '0';
    }
    
    int Hash(int x)
    {
    	return ((x ^ 1188281) + (x & 12214514)) % M;
    }
    
    int h[M + 20];
    
    int main()
    {
    	in(n); in(m);
    	if(m == 1)
    	{
    		puts("Yes"); return 0;
    	}
    	int x;
    	while(n --)
    	{
    		in(x); x = Hash(x); x = (x % M + M) % M;
    		h[x] ++;
    	}
    	int i = 0;
    	while(i < M)
    		if(h[i] % m){puts("No"); return 0;}
    		else i ++;
    	puts("Yes");
    	return 0;
    }
    
    • 1
      @ 2023-7-3 11:10:05

      答辩题

      这个题的空间限制非常紧,只能哈希做

      #include <cstdio>
      
      const int N = 2.5e6 + 20, M = 2e4 + 7;
      
      int n, m;
      char c;
      
      void in(int &x)
      {
      	c = getchar();
      	while(c > '9' || c < '0') c = getchar();
      	for(x = 0; c >= '0' && c <= '9'; c = getchar())
      		x = x * 10 + c - '0';
      }
      
      int Hash(int x)
      {
      	return ((x ^ 1188281) + (x & 12214514)) % M;
      }
      
      int h[M + 20];
      
      int main()
      {
      	in(n); in(m);
      	if(m == 1)
      	{
      		puts("Yes"); return 0;
      	}
      	int x;
      	while(n --)
      	{
      		in(x); x = Hash(x); x = (x % M + M) % M;
      		h[x] ++;
      	}
      	int i = 0;
      	while(i < M)
      		if(h[i] % m){puts("No"); return 0;}
      		else i ++;
      	puts("Yes");
      	return 0;
      }
      
      
      • 1

      信息

      ID
      229
      时间
      1500ms
      内存
      12MiB
      难度
      9
      标签
      递交数
      869
      已通过
      35
      上传者