- [KBC003F] Training
本题正确性存疑
-
035966_L3
LV 6
@
2025-1-5 20:30:22
在验题过程中，以下做法通过了本题所有原版数据：
#include <bits/stdc++.h>
using namespace std;
int x[100012], y[100012];
signed main()
{
int n, m;
cin >> n >> m;
while (m--)
{
int a, b;
cin >> a >> b;
x[a]++, y[b]++;
}
int g = 0;
for (int i = 1; i <= n; i++)
if ((x[i] + y[i]) % 2 == 1) g++;
g /= 2;
if (g % 2 == 1) g++;
cout << g << endl;
return 0;
}
但该做法明显是错误的：
样例输入 1
2 1
1 2
样例输出 1
2
样例答案 1
1
样例输入 2
3 3
1 2
2 3
3 1
样例输出 2
0
样例答案 2
1
因此本题正确性存疑。
我们在此征集可以说明本题正确 / 不正确的证据。
4 条评论
-
nr0728 LV 5 @ 2025-1-7 20:17:41出题人的解法应该是正确的，可以通过你的两个 hack，本题数据可能过水（据出题人说数据似乎是随机的），建议加强数据
-
@ 2025-1-7 20:14:29
这是出题人的解法：
#include <bits/stdc++.h> using namespace std; const int N = 1e5+5; int n,m,k,d[N]; signed main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for(int i = 1,x,y;i<=m;i++) cin>>x>>y,d[x]++,d[y]++; for(int i = 1;i<=n;i++) if(d[i]%2==1) k++; k = k/2; if((m+k)%2) k++; cout<<k; return 0; }看起来就是这样的
-
@ 2025-1-7 20:13:21
收到，此题不是我出的，我看看
- 1