A
很容易有一个错误想法，就是行从1~n，列从1~n拿，这样，第三个样例，最后，第7行，第7列，需要都增加两个数，但是(7,7)这个位置只能有一个数。
我的做法是优先队列/set队列，每次选择行、列之中当前已经有的数目最少的（这样它们最需要添加），这样能保证，行列需要添加的，不会出现只能选择多个行列一样的情况。因为优先队列的特性，剩下需要添加2个数的行/列肯定是优先被选取，它在需要添加1个数的行/列之前。
用set的话，删除一个数，要在遍历完这些数再删，
看到有3分钟做完这道题的……
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdbool>
6 #include <string>
7 #include <algorithm>
8 #include <iostream>
9 #include <sstream>
10 #include <ctime>
11 #include <stack>
12 #include <vector>
13 #include <queue>
14 #include <set>
15 #include <map>
16 #include <array>
17 #include <bitset>
18 using namespace std;
19 #define LL long long
20 #define ULL unsigned long long
21
22 const LL mod_1=1e9+7;
23 const LL mod_2=998244353;
24
25 const double eps_1=1e-5;
26 const double eps_2=1e-10;
27
28 const int maxn=1e5+10;
29
30 int row[maxn], col[maxn];
31 set<pair<int,int> > choose_col;
32 map<pair<int,int>, int > cannot;
33
34 int main()
35 {
36 int n,m,x,y,i,j,k,geshu;
37 set<pair<int,int> >::iterator z;
38 memset(row,0,sizeof(row));
39 memset(col,0,sizeof(col));
40 cannot.clear();
41 choose_col.clear();
42
43 scanf("%d%d",&n,&m);
44
45 printf("%d\n",n*m);
46
47 for (i=1;i<=m;i++)
48 {
49 scanf("%d%d",&x,&y);
50 row[x]++;
51 col[y]++;
52 cannot[make_pair(x,y)]=1;
53 printf("%d %d\n",x,y);
54 }
55
56 for (j=1;j<=n;j++)
57 if (col[j]!=m)
58 choose_col.insert(make_pair(col[y], j));
59
60 for (i=1;i<=n;i++)
61 {
62 for (j=1;j<=m-row[i];j++)
63 {
64 for (z=choose_col.begin();z!=choose_col.end();z++)
65 {
66 geshu = z->first;
67 k = z->second;
68 if (cannot[ make_pair(i, k) ]==0)
69 {
70 choose_col.erase(make_pair(geshu, k) );
71 cannot[make_pair(i, k)]=1;
72 col[k]++;
73 if (col[k]!=m)
74 choose_col.insert(make_pair(geshu+1, k));
75
76 break;
77 }
78
79 }
80 printf("%d %d\n",i, k);
81 }
82 }
83
84
85 return 0;
86 }
87 /*
88 1 1
89 1 1
90
91 ======
92
93 1 0
94
95 ======
96
97 4 0
98
99 ======
100
101 4 1
102 2 3
103 */
View Code
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdbool>
6 #include <string>
7 #include <algorithm>
8 #include <iostream>
9 #include <sstream>
10 #include <ctime>
11 #include <stack>
12 #include <vector>
13 #include <queue>
14 #include <set>
15 #include <map>
16 #include <array>
17 #include <bitset>
18 using namespace std;
19 #define LL long long
20 #define ULL unsigned long long
21
22 const LL mod_1=1e9+7;
23 const LL mod_2=998244353;
24
25 const double eps_1=1e-5;
26 const double eps_2=1e-10;
27
28 const int maxn=1e5+10;
29
30 int row[maxn], col[maxn];
31 set<pair<int,int> > choose_col;
32 map<pair<int,int>, int > cannot;
33
34 int main()
35 {
36 int n,m,x,y,i,j,k,geshu;
37 set<pair<int,int> >::iterator z;
38 memset(row,0,sizeof(row));
39 memset(col,0,sizeof(col));
40 cannot.clear();
41 choose_col.clear();
42
43 scanf("%d%d",&n,&m);
44
45 printf("%d\n",n*m);
46
47 for (i=1;i<=m;i++)
48 {
49 scanf("%d%d",&x,&y);
50 row[x]++;
51 col[y]++;
52 cannot[make_pair(x,y)]=1;
53 printf("%d %d\n",x,y);
54 }
55
56 for (j=1;j<=n;j++)
57 if (col[j]!=m)
58 choose_col.insert(make_pair(col[y], j));
59
60 for (i=1;i<=n;i++)
61 {
62 for (j=1;j<=m-row[i];j++)
63 {
64 for (z=choose_col.begin();z!=choose_col.end();z++)
65 {
66 geshu = z->first;
67 k = z->second;
68 if (cannot[ make_pair(i, k) ]==0)
69 break;
70 }
71 printf("%d %d\n",i, k);
72 choose_col.erase(make_pair(geshu, k) );
73 cannot[make_pair(i, k)]=1;
74
75 col[k]++;
76 if (col[k]!=m)
77 choose_col.insert(make_pair(geshu+1, k));
78 }
79 //cout<<"ok"<<endl;
80 }
81
82
83 return 0;
84 }
85 /*
86 1 1
87 1 1
88
89 ======
90
91 1 0
92
93 ======
94
95 4 0
96
97 ======
98
99 4 1
100 2 3
101 */
View Code
B
把数字都看成2进制分析。
其实这道题比A好写得多。
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdbool>
6 #include <string>
7 #include <algorithm>
8 #include <iostream>
9 #include <sstream>
10 #include <ctime>
11 #include <stack>
12 #include <vector>
13 #include <queue>
14 #include <set>
15 #include <map>
16 #include <array>
17 #include <bitset>
18 using namespace std;
19 #define LL long long
20 #define ULL unsigned long long
21
22 const LL mod_1=1e9+7;
23 const LL mod_2=998244353;
24
25 const double eps_1=1e-5;
26 const double eps_2=1e-10;
27
28 const int maxn=2e5+10;
29
30 LL xs[4]={6,2,4,8};
31
32 int main()
33 {
34 LL T,n,k,m,r,restn, loop, cnt_zero;
35 cin>>T;
36 while (T--)
37 {
38 cin>>n>>m>>k;
39 r=m-k;
40
41 if (m==k+1)
42 {
43 ///2^n % 2^k
44 if (n<k)
45 cout<<xs[n%4]<<endl;
46 else
47 cout<<0<<endl;
48 continue;
49 }
50 if (n<m)
51 {
52 cout<<xs[n%4]<<endl;
53 continue;
54 }
55
56 restn = n-m;
57
58 loop = restn / r;
59 cnt_zero = n - r * loop;
60 if (cnt_zero>=m)
61 cnt_zero -= r;
62
63 cout<<xs[cnt_zero%4]<<endl;
64 }
65
66 return 0;
67 }
68 /*
69 7 5 4
70 3 5 4
71 4 5 4
72 4 5 3
73 1 5 3
74
75 1 2 1
76 1 3 2
77
78
79 10 6 2
80 */
View Code
标签：atcoder,const,int,题解,LL,long,regular,include,col From： https://www.cnblogs.com/cmyg/p/18150519