Determine the Photo Position
题目描述
You have taken the graduation picture of graduates. The picture could be regarded as a matrix A of n × n n \times n n×n, each element in A is 0 or 1, representing a blank background or a student, respectively.
However, teachers are too busy to take photos with students and only took a group photo themselves. The photo could be regarded as a matrix B of 1 × m 1 \times m 1×m where each element is 2 representing a teacher.
As a master of photoshop, your job is to put photo B into photo A with the following constraints:
- you are not allowed to split, rotate or scale the picture, but only translation.
- each element in matrix B should overlap with an element in A completely, and each teacher should overlap with a blank background, not shelter from a student.
Please calculate the possible ways that you can put photo B into photo A.
输入描述:
The first line contains two integers n n n, m m m( 1 ≤ n , m ≤ 2000 1 \le n,m \le 2000 1≤n,m≤2000) indicating the size of photos A A A and B B B.
In the next n n n lines,each line contains n n n characters of ‘0’ or ‘1’,representing the matrix A A A.
The last line contains m m m characters of ‘2’, representing matrix B B B.
输出描述:
Output one integer in a line, indicating the answer.
示例1
输入
5 3
00000
01110
01110
01110
00000
222
输出
6
示例2
输入
3 2
101
010
101
22
输出
0
示例3
输入
3 1
101
010
101
2
输出
4
思路
签到题暴力判断就行了。
#include<cstdio>
using namespace std;
const int maxn=2020;
int n,m,ans,ch;
char str[maxn],mp[maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
scanf("%s",str);
for(int i=1;i<=n;i++){
int pos=0;
for(int j=1;j<=n;j++){
if(mp[i][j]=='0'){
pos++;
if(pos>=m) ans++;
}else pos=0;
}
}
printf("%d\n",ans);
}
其他做法
滑动窗口类似的方法。
#include<cstdio>
using namespace std;
const int maxn=2010;
int n,m,mp[maxn][maxn],ans;
char ch;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf(" %c",&ch),mp[i][j]=ch-'0';
for(int i=1;i<=n;i++){
int sum=0;
for(int j=1;j<=m;j++) sum+=mp[i][j];
for(int j=1;j+m-1<=n;j++)
ans+=!sum,sum+=mp[i][j+m]-mp[i][j];
}
printf("%d\n",ans);
}
Find 3-friendly Integers
题目描述
A positive integer is 3-friendly if and only if we can find a continuous substring in its decimal representation, and the decimal integer represented by the substring is a multiple of 3 3 3.
For instance:
- 104 104 104 is 3-friendly because “ 0 0 0” is a substring of “ 104 104 104” and 0 m o d 3 = 0 0 \mod 3 = 0 0mod3=0.
- 124 124 124 is 3-friendly because “ 12 12 12” is a substring of “ 124 124 124” and 12 m o d 3 = 0 12 \mod 3 = 0 12mod3=0. “ 24 24 24” is also a valid substring.
- 17 17 17 is not 3-friendly because 1 m o d 3 ≠ 0 1 \mod 3 \ne 0 1mod3=0, 7 m o d 3 ≠ 0 7 \mod 3 \ne 0 7mod3=0, 17 m o d 3 ≠ 0 17 \mod 3 \ne 0 17mod3=0.
Note that the substring with leading zeros is also considered legal.
Given two integers L L L and R R R, you are asked to tell the number of positive integers x x x such that L ≤ x ≤ R L \le x \le R L≤x≤R and x x x is 3-friendly.
输入描述:
There are multiple test cases. The first line of the input contains an integer T ( 1 ≤ T ≤ 10000 ) T(1 \le T \le 10000) T(1≤T≤10000), indicating the number of test cases. For each test case:
The only line contains two integers L , R L,R L,R ( 1 ≤ L ≤ R ≤ 1 0 18 ) (1 \le L \le R \le 10^{18}) (1≤L≤R≤1018), indicating the query.
输出描述:
For each test case output one line containing an integer, indicating the number of valid x x x.
示例1
输入
3
4 10
1 20
1 100
输出
3
11
76
思路
首先找出1到100之间符合要求的数字，找找规律：
显然它是有一定的规律的，接着找找101到200规律：
发现101到200之间的数字居然全部满足题目要求。结合第一张图，可以推出结论，201到300之间的数字也全满足，301到400自然也全满足。
进而可以得出100以上的数字全都满足题目要求。
把1到100之间满足要求的数统计一下，就可以计算结果了。 [ l , r ] [l,r] [l,r]之间的数量可以通过 [ 1 , r ] [1,r] [1,r]减去 [ 1 , l − 1 ] [1,l-1] [1,l−1]得出。
#include<cstdio>
#include<algorithm>
using namespace std;
const int a[200]={1,
1,1,0,1,1,0,1,1,0,0,
1,0,0,1,0,0,1,0,0,0,
0,1,0,0,1,0,0,1,0,0,
0,0,0,0,0,0,0,0,0,0,
1,0,0,1,0,0,1,0,0,0,
0,1,0,0,1,0,0,1,0,0,
0,0,0,0,0,0,0,0,0,0,
1,0,0,1,0,0,1,0,0,0,
0,1,0,0,1,0,0,1,0,0,
0,0,0,0,0,0,0,0,0,0};
int pre[110];
long long calc(long long x){
if(x<=100) return pre[(int)x];
else return x-100+pre[100];
}
void solve(){
for(int i=1;i<=100;i++)
if(a[i]==0) pre[i]=pre[i-1]+1;
else pre[i]=pre[i-1];
long long l,r,ans1,ans2;
scanf("%lld%lld",&l,&r);
if(l>r) swap(l,r);
ans1=calc(l-1);
ans2=calc(r);
printf("%lld\n",ans2-ans1);
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
}
其他做法
刚开始预处理出所有不满足要求的数字，之后的每次询问，依次遍历每个不满足要求的数，若在给定区间内， s u m sum sum减一。
#include<bits/stdc++.h>
using namespace std;
int T;
vector<int> pot={1,2,4,5,7,8};
int main(){
for(int i=11;i<100;i++)
if(i%3!=0&&i%10%3!=0&&i/10%3!=0)
pot.push_back(i);
for(cin>>T;T;T--){
long long l,r,sum;
cin>>l>>r;
sum=r-l+1;
for(int o:pot) if(o>=l&&o<=r) sum--;
cout<<sum<<endl;
}
}
Ball Dropping
题目描述
A standard sphere ball is falling in the air, and the center of the sphere is exactly on the centerline of an empty isosceles trapezoidal. The trapezoid is hanging horizontally under the sphere.
Please determine whether the ball will get stuck in the trapezoid or drop past the trapezoid.
输入描述:
The input contains four integers r , a , b , h r, a, b, h r,a,b,h ( 1 ≤ r , a , b , h ≤ 1000 , a > b ) (1 \le r,a,b,h \le 1000, a > b) (1≤r,a,b,h≤1000,a>b), indicating the radius of the ball, the top base, the bottom base, and the height of the isosceles trapezoid.
It is guaranteed that 2 r ≠ b 2r \ne b 2r=b, 2 r < a 2r < a 2r<a, 2 r < h 2r < h 2r<h .
输出描述:
Output ‘Drop’ if the sphere ball will drop past the empty trapezoid, otherwise output ‘Stuck’.
If the answer is ‘Stuck’, please also calculate the stuck position(the height between the center of the sphere and the midpoint of the bottom base). Your answer is considered correct if its absolute or relative error does not exceed 1 0 − 6 10^{-6} 10−6 .
示例1
输入
2 8 2 5
输出
Stuck
2.2206345966
示例2
输入
1 8 3 5
输出
Drop
思路
主要研究图中阴影部分：
把它补为一个三角形，设一条直角边长度为
x
x
x，可以算出
x
=
b
h
a
−
b
x=\frac{bh}{a-b}
x=a−bbh，根据相似三角形，可得所求答案为
2
r
b
x
2
+
b
2
4
−
x
\frac{2r}{b}\sqrt{x^2+\frac{b^2}{4}}-x
b2rx2+4b2
−x.
#include<cstdio>
#include<cmath>
using namespace std;
int r,a,b,h;
int main(){
scanf("%d%d%d%d",&r,&a,&b,&h);
if(2*r<b){puts("Drop");return 0;}
else puts("Stuck");
double x=(1.0*b*h)/(a-b);
double ans=2.0*r/b*sqrt(1.0*x*x+b*b/4.0)-x;
printf("%.8lf",ans);
}
其他做法
可以用三角函数来做：
设那个比较大的锐角为 α \alpha α，那么 t a n α = h a − b 2 = 2 h a − b tan\alpha=\frac{h}{\frac{a-b}{2}}=\frac{2h}{a-b} tanα=2a−bh=a−b2h，要求的答案为 r c o s α − b h a − b \frac{r}{cos\alpha}-\frac{bh}{a-b} cosαr−a−bbh。
#include<bits/stdc++.h>
using namespace std;
double r,a,b,h;
int main(){
cin>>r>>a>>b>>h;
if(2*r<b){puts("Drop");return 0;}
double ans=r/cos(atan(2*h/(a-b)))-b*h/(a-b);
printf("Stuck\n%.10lf\n",ans);
}
Alice and Bob
题目描述
Alice and Bob like playing games. There are two piles of stones with numbers n n n and m m m. Alice and Bob take turns to operate, each operation can take away k k k ( k > 0 ) (k>0) (k>0) stones from one pile and take away s × k s \times k s×k ( s ≥ 0 ) (s \geq 0) (s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game.
Please determine who will win the game if both Alice and Bob play the game optimally.
输入描述:
The first line contains an integer T ( 1 ≤ T ≤ 1 0 4 ) T(1 \le T \le 10^4) T(1≤T≤104) denotes the total number of test cases.
Each test case contains two integers n , m n,m n,m ( 1 ≤ n , m ≤ 5 × 1 0 3 ) (1 \le n,m \leq 5 \times 10^3) (1≤n,m≤5×103) in a line, indicating the number of two piles of stones.
输出描述:
For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.
输入
5
2 3
3 5
5 7
7 5
7 7
输出
Bob
Alice
Bob
Bob
Alice
思路
首先发现 { 3 , 2 } \{3,2\} {3,2}先手必败（ { 2 , 3 } \{2,3\} {2,3}也是，后面省略对称部分），那么，所有可以一步推导为 { 3 , 2 } \{3,2\} {3,2}的就是先手必胜。能一步推导为 { 3 , 2 } \{3,2\} {3,2}的状态 { x , y } \{x,y\} {x,y}有一个规律：
- ( x − 2 ) ∣ ( y − 3 ) (x-2)|(y-3) (x−2)∣(y−3)或 ( x − 3 ) ∣ ( y − 2 ) (x-3)|(y-2) (x−3)∣(y−2).
a ∣ b a|b a∣b代表 a a a可以整除 b b b.
通过 { 3 , 2 } \{3,2\} {3,2}这个状态，可以得到 { 7 , 5 } \{7,5\} {7,5}也是先手必败，把 { 7 , 5 } \{7,5\} {7,5}也加入到集合中，之后，不断利用已有的必败状态，推导出新的必败状态。
打个表把结果存在数组里。
//打表代码
#include<cstdio>
using namespace std;
const int maxn=5010;
int mp[maxn][2],tot;
bool check(int x,int y){
if(x==0||y==0||x==y||x%y==0||y%x==0) return false;
for(int i=0;i<tot;i++){
if(x==mp[i][0]&&y==mp[i][1]||x==mp[i][1]&&y==mp[i][0]) return true;
int a=x-mp[i][0],b=y-mp[i][1];
if(a==0||b==0) return false;
if(a>0&&b>0&&(a%b==0||b%a==0)) return false;
a=x-mp[i][1],b=y-mp[i][0];
if(a==0||b==0) return false;
if(a>0&&b>0&&(a%b==0||b%a==0)) return false;
}
return true;
}
int main(){
mp[0][0]=3,mp[0][1]=2,tot=1;
for(int i=1;i<=5000;i++)
for(int j=1;j<i;j++) if(check(i,j))
mp[tot][0]=i,mp[tot++][1]=j;
for(int i=0;i<tot;i++)
printf(",{%d,%d}",mp[i][0],mp[i][1]);
printf("\ntot=%d\n",tot);
}
上面这个代码大概跑个半分钟能计算出5000之内所有的必败状态。
比较失策的是 3 , 2 {3,2} 3,2重复计算了两次，不过不影响结果。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5010;
int mp[maxn][2]={{3,2},{7,5},{12,9},{15,11},{20,14},{22,17},{32,24},{33,19},{35,26},{38,31},{40,29},{52,42},{53,37},{58,28},{60,45},{62,50},{65,47},{68,55},{70,49},{75,44},{79,57},{86,67},{87,64},{92,72},{99,74},{101,77},{110,83},{113,85},{116,90},{118,82},{123,89},{126,97},{127,95},{129,94},{136,103},{145,108},{146,106},{156,139},{160,122},{161,120},{164,125},{166,112},{174,81},{177,133},{180,138},{182,132},{186,143},{190,142},{195,149},{197,152},{198,135},{199,105},{203,148},{215,168},{218,158},{224,172},{228,171},{229,163},{232,154},{236,185},{239,141},{241,192},{246,115},{253,184},{256,194},{259,189},{264,208},{266,201},{268,188},{271,210},{274,207},{278,214},{280,221},{281,205},{286,170},{289,217},{298,179},{301,226},{305,252},{306,248},{307,234},{309,131},{313,245},{315,223},{317,213},{321,250},{322,212},{325,244},{327,220},{332,231},{339,255},{340,151},{346,261},{350,176},{358,276},{359,263},{362,285},{367,293},{370,283},{372,238},{375,270},{379,288},{386,296},{390,295},{391,243},{408,319},{411,312},{415,303},{432,300},{435,329},{445,345},{446,343},{449,338},{454,334},{456,291},{461,352},{464,311},{467,349},{470,384},{474,395},{478,361},{479,357},{483,400},{485,388},{487,399},{489,337},{494,364},{496,342},{501,324},{505,377},{509,374},{511,397},{518,393},{520,369},{521,273},{525,423},{527,366},{529,421},{530,407},{531,405},{532,356},{537,413},{541,420},{545,336},{549,434},{553,382},{556,443},{557,419},{558,348},{560,427},{565,258},{568,410},{570,431},{574,437},{577,355},{580,425},{586,417},{588,402},{590,354},{596,460},{600,440},{601,404},{603,439},{610,469},{614,448},{620,453},{624,430},{632,473},{635,492},{639,381},{646,499},{648,508},{649,504},{651,452},{653,503},{658,516},{660,481},{661,463},{664,515},{666,466},{671,459},{673,498},{683,442},{691,477},{693,564},{697,551},{702,331},{711,555},{716,514},{719,429},{722,595},{723,543},{726,491},{735,540},{737,567},{740,523},{744,572},{748,585},{752,539},{760,476},{761,472},{766,576},{768,583},{771,563},{772,458},{776,513},{778,634},{780,579},{785,628},{787,619},{788,507},{799,626},{800,548},{805,594},{810,607},{811,593},{818,622},{822,617},{825,547},{827,644},{828,599},{831,616},{836,630},{842,612},{845,606},{849,609},{855,535},{857,676},{866,605},{869,685},{870,663},{871,451},{876,657},{877,592},{879,637},{883,695},{886,641},{892,710},{893,534},{896,680},{899,643},{904,679},{910,706},{912,678},{917,730},{918,656},{920,689},{924,732},{929,669},{935,714},{937,700},{944,751},{946,699},{948,704},{956,794},{957,708},{964,687},{969,718},{976,721},{982,750},{985,675},{986,582},{989,668},{991,763},{995,757},{996,713},{1000,747},{1007,743},{1010,728},{1013,756},{1017,774},{1020,754},{1023,797},{1029,796},{1032,782},{1036,742},{1038,765},{1040,816},{1046,655},{1053,833},{1055,864},{1061,791},{1062,739},{1065,746},{1070,824},{1072,803},{1076,853},{1079,808},{1081,807},{1082,790},{1085,784},{1090,793},{1098,830},{1102,875},{1106,852},{1107,682},{1110,815},{1117,814},{1118,813},{1120,848},{1122,835},{1130,863},{1131,820},{1145,859},{1150,770},{1156,868},{1164,885},{1165,839},{1167,734},{1175,882},{1180,862},{1186,890},{1190,851},{1192,888},{1194,881},{1201,838},{1202,562},{1206,861},{1208,906},{1211,902},{1212,874},{1214,915},{1219,943},{1225,847},{1227,898},{1231,909},{1241,844},{1243,927},{1245,914},{1248,973},{1254,954},{1261,908},{1265,950},{1268,940},{1269,923},{1274,931},{1279,967},{1284,978},{1285,895},{1292,1027},{1295,963},{1297,960},{1302,972},{1307,933},{1311,959},{1314,952},{1317,984},{1322,841},{1329,994},{1331,1051},{1334,1043},{1336,1002},{1337,971},{1346,1006},{1348,981},{1358,725},{1361,1012},{1363,926},{1366,1009},{1371,1035},{1372,999},{1376,1025},{1378,993},{1381,942},{1384,873},{1387,1045},{1389,1034},{1390,966},{1394,922},{1397,1089},{1400,1005},{1403,1144},{1405,939},{1408,1060},{1413,1069},{1414,1058},{1419,1019},{1420,962},{1425,1100},{1428,1078},{1432,1016},{1438,1140},{1443,1096},{1446,1064},{1449,1125},{1451,988},{1455,1094},{1457,1088},{1458,1048},{1461,1004},{1464,1104},{1465,1015},{1468,1092},{1470,1143},{1477,1022},{1481,1109},{1484,1116},{1491,1174},{1492,1075},{1499,1087},{1502,1137},{1509,1134},{1510,1124},{1514,1074},{1516,1129},{1521,1068},{1525,1161},{1527,1042},{1529,1159},{1532,1136},{1534,1155},{1536,1153},{1537,1139},{1539,1113},{1541,1152},{1543,1067},{1547,980},{1560,1183},{1561,1169},{1563,1142},{1569,1158},{1575,1133},{1577,1178},{1580,1239},{1581,1149},{1590,1197},{1592,1163},{1599,598},{1605,1247},{1606,1112},{1611,1188},{1612,1171},{1617,1229},{1619,1173},{1622,1238},{1625,1217},{1626,1127},{1633,1031},{1636,1200},{1640,1221},{1643,1237},{1651,1236},{1653,1199},{1661,1258},{1664,1283},{1665,1185},{1674,1148},{1678,1235},{1679,1204},{1682,1281},{1684,1290},{1687,1084},{1692,1278},{1694,1276},{1695,1057},{1702,1289},{1707,1272},{1708,1260},{1710,1301},{1713,1264},{1717,1224},{1721,1253},{1729,1327},{1730,1233},{1736,1216},{1746,1251},{1754,1320},{1756,1300},{1758,1115},{1762,1357},{1765,1305},{1767,1316},{1769,1263},{1772,1418},{1774,1310},{1777,802},{1782,1344},{1785,1340},{1787,1325},{1795,1267},{1799,1257},{1802,1343},{1811,1319},{1812,998},{1820,1250},{1822,1339},{1824,1380},{1825,1304},{1831,1354},{1832,1309},{1837,1430},{1838,1360},{1842,1352},{1845,1299},{1847,1416},{1850,1342},{1854,759},{1859,1370},{1863,1392},{1866,1294},{1869,1442},{1877,1410},{1878,1369},{1879,1365},{1882,1287},{1884,1368},{1888,1356},{1901,1396},{1904,1386},{1906,1196},{1914,1407},{1919,1383},{1922,1475},{1923,1437},{1929,1223},{1935,1422},{1941,1480},{1942,1472},{1947,1460},{1949,1448},{1953,1436},{1964,1495},{1966,1402},{1970,1505},{1972,1520},{1975,1434},{1978,1399},{1981,1508},{1986,1504},{1992,1494},{1994,1441},{1997,1497},{2001,1571},{2003,1507},{2004,1271},{2007,1453},{2011,1463},{2018,901},{2026,1487},{2029,1555},{2030,1490},{2031,1479},{2033,1554},{2036,1375},{2040,1424},{2042,1412},{2050,1566},{2051,1440},{2056,1546},{2059,1524},{2067,1565},{2070,1551},{2076,1531},{2077,1177},{2080,1589},{2085,1597},{2088,1513},{2094,1550},{2096,1518},{2098,1501},{2100,1588},{2103,1579},{2105,1568},{2107,1489},{2116,1557},{2129,1553},{2132,1704},{2134,1483},{2137,1587},{2140,1333},{2142,1604},{2145,1630},{2148,1586},{2152,1603},{2161,1574},{2163,1741},{2168,1594},{2174,1670},{2176,1616},{2180,1584},{2182,1657},{2184,1621},{2191,1512},{2193,1663},{2194,1628},{2195,1601},{2198,1614},{2202,1673},{2203,1610},{2205,1474},{2209,1445},{2215,1256},{2217,1659},{2222,1691},{2224,1642},{2229,1638},{2230,1467},{2234,1701},{2237,1690},{2239,1650},{2246,1712},{2254,1751},{2255,1648},{2256,1573},{2261,1700},{2268,1699},{2271,1681},{2276,1647},{2281,1609},{2283,1728},{2287,1706},{2288,1351},{2293,1672},{2297,1698},{2298,1646},{2302,1635},{2310,1655},{2317,1761},{2318,1745},{2322,1724},{2329,1608},{2332,1805},{2335,1726},{2338,1583},{2341,1719},{2345,1753},{2347,1676},{2350,1744},{2356,1669},{2358,1790},{2362,1743},{2365,1814},{2366,1668},{2368,1723},{2369,1050},{2375,1798},{2376,1732},{2381,1776},{2385,1781},{2388,1324},{2390,1545},{2393,1792},{2395,1873},{2398,1818},{2400,1817},{2402,1789},{2404,1794},{2406,1764},{2411,1780},{2415,1830},{2420,1808},{2421,1549},{2426,1760},{2427,1738},{2435,1807},{2437,1689},{2439,1716},{2444,1858},{2449,1784},{2453,1749},{2455,1210},{2459,1835},{2462,1891},{2469,1828},{2473,1810},{2485,1849},{2490,1740},{2492,1927},{2493,1844},{2495,1735},{2502,1876},{2505,1871},{2509,1909},{2511,1897},{2513,1865},{2515,1900},{2516,1804},{2523,1841},{2525,1890},{2530,1913},{2538,1771},{2546,1989},{2548,1940},{2549,1926},{2550,1925},{2551,1857},{2556,2013},{2557,1779},{2564,1911},{2567,1903},{2570,1938},{2572,1894},{2575,1917},{2576,1881},{2592,1916},{2597,1937},{2600,1899},{2604,1147},{2607,1715},{2611,1974},{2613,1862},{2616,1959},{2623,1182},{2627,2039},{2632,1958},{2634,1834},{2640,1667},{2642,1934},{2645,1983},{2647,1956},{2657,1486},{2661,1944},{2665,1933},{2668,2048},{2669,1624},{2671,2025},{2673,1977},{2675,1955},{2682,2009},{2684,2016},{2687,1988},{2689,1952},{2691,1969},{2700,1932},{2702,2021},{2704,1999},{2707,1991},{2708,1921},{2709,1896},{2720,1856},{2729,2015},{2733,2058},{2738,1985},{2743,1893},{2746,2092},{2747,2055},{2749,2047},{2751,1840},{2754,2066},{2758,2111},{2759,2062},{2761,1963},{2768,2091},{2773,1886},{2778,2128},{2779,2023},{2780,1996},{2785,2045},{2788,2119},{2789,1951},{2792,2165},{2798,2087},{2804,2114},{2806,2064},{2809,2074},{2810,1313},{2814,2158},{2816,2072},{2826,2126},{2830,1875},{2832,2038},{2834,2125},{2836,1374},{2840,1350},{2843,2173},{2846,2187},{2850,2079},{2856,2084},{2862,2155},{2864,2110},{2869,2151},{2873,2170},{2879,1852},{2881,2147},{2882,2139},{2883,2113},{2891,2102},{2899,2124},{2902,2069},{2905,2212},{2910,1797},{2915,2200},{2917,2179},{2919,2160},{2921,2122},{2925,2121},{2927,2178},{2931,1961},{2938,2020},{2943,2167},{2946,2219},{2953,1968},{2954,1645},{2956,2090},{2957,1827},{2960,2236},{2970,2154},{2972,2233},{2974,2244},{2979,2260},{2981,1427},{2985,2189},{2986,1980},{2993,2265},{2997,2228},{3001,2249},{3004,2275},{3006,2270},{3007,2242},{3012,2328},{3015,2227},{3020,2172},{3024,2214},{3026,2253},{3031,2285},{3032,2274},{3036,2208},{3037,2061},{3039,2150},{3046,2267},{3048,2028},{3057,2295},{3061,2241},{3064,2232},{3067,2207},{3078,2006},{3082,2321},{3084,2301},{3089,2252},{3097,2280},{3099,2259},{3101,2354},{3103,2417},{3106,2380},{3110,2258},{3113,2331},{3116,2431},{3117,2324},{3118,2312},{3119,2248},{3121,2044},{3125,2306},{3128,2316},{3130,2308},{3138,2109},{3145,2344},{3148,2251},{3156,1748},{3159,1559},{3163,2305},{3169,2384},{3172,2290},{3177,2374},{3179,2413},{3182,2392},{3190,2409},{3193,2300},{3197,2353},{3201,2383},{3202,2334},{3206,2465},{3207,2083},{3213,2379},{3217,2361},{3218,2320},{3225,2434},{3229,2226},{3232,2452},{3235,1734},{3241,2561},{3244,2197},{3246,2472},{3247,2373},{3250,2326},{3252,1801},{3254,2082},{3258,2423},{3261,2221},{3269,2446},{3273,1861},{3281,2451},{3286,2484},{3287,2479},{3289,2372},{3294,2489},{3297,2488},{3299,2475},{3302,2443},{3303,1523},{3312,2587},{3314,2387},{3317,2442},{3323,2537},{3325,2499},{3327,2441},{3333,2292},{3334,2131},{3335,1686},{3338,2273},{3341,2433},{3343,2586},{3345,2482},{3350,2521},{3351,2457},{3355,2508},{3358,2507},{3359,2408},{3367,2654},{3368,2529},{3372,2595},{3374,2520},{3377,2582},{3379,2533},{3381,2519},{3384,2501},{3385,1596},{3391,2555},{3393,2429},{3395,2554},{3396,2343},{3405,2544},{3409,2594},{3412,2532},{3413,2467},{3418,2626},{3422,2569},{3423,2360},{3425,2314},{3433,2263},{3441,2518},{3449,2652},{3454,2581},{3459,2580},{3460,2304},{3463,2638},{3464,2609},{3466,2599},{3467,2579},{3471,2527},{3475,2585},{3478,2186},{3480,2637},{3488,2543},{3495,2498},{3498,2487},{3500,2481},{3502,2566},{3506,2664},{3508,2630},{3510,2563},{3512,2419},{3518,2606},{3519,2352},{3525,2621},{3529,2680},{3534,2535},{3536,2578},{3538,2560},{3544,2542},{3547,2651},{3549,2718},{3552,2461},{3558,2602},{3560,1632},{3565,2696},{3569,2659},{3570,2340},{3578,2629},{3584,2656},{3585,2371},{3589,2279},{3592,2559},{3598,2478},{3600,2723},{3601,2620},{3605,2619},{3614,2694},{3619,2712},{3621,2644},{3628,2618},{3635,2726},{3638,2699},{3640,2706},{3643,2717},{3647,2742},{3651,2737},{3656,2791},{3658,2679},{3665,2715},{3667,2636},{3671,2650},{3673,2757},{3676,2741},{3681,2782},{3684,2584},{3689,2736},{3693,2541},{3698,2765},{3699,2574},{3704,2802},{3705,2775},{3709,2771},{3712,1816},{3714,2795},{3719,2756},{3720,2678},{3722,2590},{3724,2829},{3727,2732},{3731,2378},{3733,2801},{3737,2867},{3739,2625},{3743,2818},{3748,2677},{3756,2825},{3759,2735},{3762,2800},{3763,2349},{3767,2876},{3769,2808},{3771,2823},{3772,2667},{3776,2861},{3777,2855},{3781,2860},{3787,2813},{3793,2839},{3795,2968},{3798,2941},{3801,2898},{3809,2866},{3810,2397},{3811,2144},{3814,2728},{3821,3076},{3822,2909},{3824,2853},{3825,2767},{3832,2740},{3835,2895},{3838,2540},{3841,2940},{3844,2698},{3848,2812},{3852,2731},{3854,2820},{3859,975},{3862,2794},{3864,2477},{3872,2930},{3877,3066},{3880,2889},{3882,2859},{3886,2849},{3888,2845},{3890,2784},{3896,2967},{3898,2745},{3900,2886},{3907,2875},{3908,2211},{3914,3030},{3916,2912},{3917,2753},{3921,2964},{3923,2936},{3924,2553},{3927,2929},{3932,2848},{3935,2907},{3941,2504},{3944,2950},{3948,2948},{3952,3011},{3955,2858},{3957,2797},{3961,3055},{3965,2996},{3966,2978},{3971,2914},{3974,2770},{3977,2711},{3982,2977},{3991,1868},{3995,2901},{3998,2983},{3999,2838},{4010,3017},{4011,2893},{4012,2777},{4016,3051},{4017,3010},{4018,2693},{4026,3150},{4027,2952},{4030,1931},{4033,3081},{4037,3019},{4038,2364},{4044,2878},{4049,3060},{4051,3043},{4052,2763},{4055,2157},{4057,3074},{4060,3000},{4068,3187},{4070,3035},{4074,2995},{4075,2828},{4079,1908},{4081,2991},{4082,2966},{4089,2649},{4097,3053},{4100,3087},{4103,3023},{4107,3034},{4109,2924},{4111,3041},{4119,3123},{4120,3094},{4121,2990},{4125,2615},{4128,3045},{4135,2934},{4138,2959},{4140,3086},{4141,3029},{4146,3137},{4150,3072},{4151,2976},{4152,2945},{4154,2497},{4160,2963},{4162,2714},{4165,3280},{4169,3153},{4172,3212},{4173,3127},{4176,3028},{4181,3542},{4182,3165},{4184,3133},{4186,2872},{4192,2933},{4195,3136},{4197,2923},{4199,2962},{4209,3147},{4210,3143},{4219,3093},{4222,3115},{4223,3096},{4231,2989},{4234,3092},{4237,3009},{4240,2448},{4243,3158},{4247,3195},{4249,3050},{4253,3152},{4261,3211},{4262,3140},{4263,3080},{4270,3278},{4271,3175},{4272,3162},{4277,3216},{4278,3069},{4288,3320},{4290,3265},{4291,3189},{4296,3192},{4298,3331},{4300,3181},{4302,3003},{4305,3239},{4307,3204},{4310,3272},{4314,3215},{4317,3337},{4319,3221},{4324,3105},{4330,3063},{4336,2904},{4338,3209},{4341,3285},{4343,3220},{4345,3257},{4348,3199},{4356,3275},{4361,3168},{4363,2999},{4372,3400},{4373,3234},{4375,3237},{4383,3361},{4384,3310},{4390,2871},{4395,3184},{4398,3432},{4399,3387},{4416,3329},{4425,3231},{4428,3607},{4429,3132},{4434,3404},{4437,3453},{4438,3383},{4442,3309},{4443,3014},{4446,3228},{4447,3091},{4449,3108},{4452,3308},{4453,3306},{4454,3249},{4466,3316},{4468,3399},{4471,3256},{4473,3293},{4478,3430},{4479,2725},{4487,3438},{4489,3407},{4493,3291},{4495,3227},{4503,3112},{4506,3224},{4507,2425},{4511,3322},{4519,3357},{4522,3364},{4523,3349},{4525,3366},{4526,3283},{4528,3243},{4532,3398},{4539,3277},{4543,3171},{4546,3296},{4547,3268},{4549,3271},{4550,2852},{4552,3371},{4559,3402},{4563,3167},{4567,3452},{4571,3443},{4572,1697},{4578,3469},{4579,3411},{4581,3264},{4586,3596},{4593,2035},{4595,3458},{4599,3448},{4601,3436},{4605,3429},{4608,2787},{4610,3260},{4619,2663},{4621,3486},{4622,3390},{4628,3483},{4631,3421},{4635,3348},{4644,3568},{4650,3370},{4652,3613},{4657,3521},{4660,3482},{4663,3347},{4670,3447},{4674,3492},{4675,3446},{4678,3301},{4681,3497},{4683,3174},{4690,3435},{4691,3428},{4700,3059},{4705,3562},{4706,2118},{4708,3477},{4712,3440},{4717,3491},{4722,3532},{4725,3417},{4732,3750},{4733,3485},{4740,3577},{4742,3515},{4744,3354},{4745,2842},{4751,3517},{4761,3528},{4763,3524},{4765,3625},{4768,3580},{4771,3663},{4772,3595},{4773,3551},{4775,3686},{4778,3583},{4779,2988},{4782,2897},{4786,3574},{4789,3540},{4801,3609},{4803,3457},{4805,2053},{4807,3634},{4809,3494},{4810,3415},{4814,3645},{4815,2722},{4818,3594},{4821,3623},{4832,3557},{4836,3514},{4839,3603},{4845,3637},{4847,3505},{4850,3555},{4856,3474},{4865,3669},{4871,3617},{4876,3527},{4878,3662},{4882,3490},{4888,3675},{4889,3612},{4892,3473},{4897,3427},{4903,3717},{4907,3655},{4914,3389},{4921,3576},{4926,3633},{4928,3591},{4932,3726},{4935,3631},{4939,3616},{4941,3567},{4945,3462},{4948,3692},{4953,3753},{4956,3680},{4959,3654},{4967,3588},{4969,3531},{4972,3661},{4977,3642},{4979,3582},{4992,3223},{5000,3742}};
void solve(){
int x,y;
scanf("%d%d",&x,&y);
if(x<y) swap(x,y);
for(int i=0;i<1359;i++)
if(mp[i][0]==x&&mp[i][1]==y){
puts("Bob");return;
}
puts("Alice");
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
}
其他做法
类似于埃氏筛法的一种打表方法。上面第一种方法把 { 2 , 3 } \{2,3\} {2,3}作为最初的必败状态，这种方法把 { 0 , 0 } \{0,0\} {0,0}作为最初的必败状态。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
bitset<maxn> f[maxn];
int main(){
for(int sum=0;sum<=10005;sum++)
for(int i=max(0,sum-5000),j=sum-i;i<=5000&&j>=0;i++,j--)
if(f[i][j]==0){
for(int l=1;i+l<=5000;l++)
for(int k=0;j+k*l<=5000;k++)
f[i+l][j+k*l]=1;
for(int l=1;j+l<=5000;l++)
for(int k=0;i+k*l<=5000;k++)
f[i+k*l][j+l]=1;
}
int T,x,y;
for(cin>>T;T;T--){
cin>>x>>y;
puts(f[x][y]?"Alice":"Bob");
}
}