• 2024Xtu程设第一次练习题解

    程设练习题谢大会专门查重

    1.1531奇怪的数字

    题目让我们从小到大输出1e6以内所有的答案，其实也没什么好的思路

    就是将一个数n的所有位都拆出来，遍历这些位（每次取一个x），然后通过作除法（y = n / x）得到另一个值y

    如果y的构成与去掉x之后的n一样，那n就是满足条件的答案。

    1. #include
    2. #include
    3. const int maxn = 1000000;
    4. using namespace std;
    5. bool solve(int n) {
    6.     vector<int>TMP(10,0);
    7.     int var = n,cnt = 0;
    8.     while(var) {
    9.         TMP[var%10]++;
    10.         var/=10;
    11.         cnt++;
    12.     }
    13.     for(int i = 9; i>=2; i--) {
    14.         if(!TMP[i] || n%i !=0)continue;
    15.         int y = n/i,N = 0;
    16.         bool sign = true;
    17.         vector<int>v(TMP);
    18.         v[i]--;
    19.         while(y) {
    20.             if((--v[y%10])<0) {
    21.                 sign = false;
    22.                 break;
    23.             }
    24.             N++;
    25.             y/=10;
    26.         }
    27.         if(N!=cnt-1)sign = false;
    28.         if(sign) return true;
    29.     }
    30.     return false;
    31. }
    32. int main() {
    33.     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    34.     for(int i = 126; i<=maxn; i++) {
    35.         if(solve(i))cout<"\n";
    36.     }
    37. }

    2.1542数列

    这个生成函数其实比较类似之前做过的某种题，那题对时间复杂度要求更高，要求先对生成式的各个系数进行分类讨论，然后加上局部暴力求解

    这题似乎直接暴力生成，一旦遇到了生成过的就break，注意0无论什么时候都会被第一个生成（S0=0）

    1. #include
    2. #include
    3. #define ll long long
    4. using namespace std;
    5. ll a,b,m;
    6. ll solve(){
    7.     vector<int>vis(m+1,0);
    8.         vis[0]++;
    9.     ll pre = 0;
    10.     while(1){ 
    11.         pre = (a*pre+b)%m;
    12.         if(vis[pre])break;
    13.         vis[pre]++;
    14.     }
    15.     for(int i = 0;i<=m;i++){
    16.         if(vis[i]==0)return i;    
    17.     }
    18. }
    19. int main() {
    20.     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    21.     int t;
    22.     cin>>t;
    23.     while(t--){
    24.         cin>>a>>b>>m;
    25.         cout<<solve()<<"\n";
    26.     }
    27. }

    3.1548回文串

    硬模拟每个位置添加万能字符（'#'），再双指针验证答案正确性即可

    1. #include
    2. #include
    3. using namespace std;
    4. char buf[1010];
    5. string tmp;
    6. bool check(string var){
    7.     int l = 0,r = var.size()-1;
    8.     while(l
    9.         if(var[l] == var[r] || var[l]=='#' || var[r] == '#'){
    10.             l++;r--;
    11.         }else return false;
    12.     }
    13.     return true;
    14. }
    15. int solve(){
    16.     int ans = 0;
    17.     for(int i = 0;i<=tmp.size();i++){
    18.         string var = tmp;
    19.         var.insert(i,1,'#');
    20.         ans += check(var);
    21.     }
    22.     return ans;
    23. }
    24. int main(){
    25.     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    26.     while(scanf("%s",buf)!=EOF){
    27.         tmp.clear();
    28.         for(int i = 0;buf[i]!='\0';i++){
    29.             tmp+=buf[i];
    30.         }
    31.         cout<<solve()<<"\n";
    32.     }
    33.     return 0;
    34. }

    4.1549 2的幂次I

    首先对时间复杂度判断，直接双重循环O(n²)明显不行

    然后我们肯定是要预处理2的次方的，存入一个数组中，最大值为刚刚超过2e9，作为边界值

    这时候明显可以根据2的k次方，以及我们遍历的一个tmp[i]，用减法得到另一个数y，因为要保证下标i

    （2的k次方小于等于tmp[i]时肯定不用找，又因为j下标大于i，题目保证数据的递增性，所以2的k次方起码满足2^k>2*tmp[i]才进行查找）

    我一开始直接用map，预先将每个值映射为对应的下标，但好像这样会高频率的访问，导致耗时较多，这里看了谢大的题解，用二分查找，也是勉强过了

    1. #include
    2. #define ll long long
    3. using namespace std;
    4. int cnt = 1, n;
    5. const int maxn = 1e5 + 2;
    6. ll mol[32];
    7. ll tmp[maxn];
    8. bool get(int l,int target){
    9.     int r = n-1;
    10.     while(l<=r){
    11.         int mid = (l+r)>>1;
    12.         if(tmp[mid]1;
    13.         else r=mid-1;
    14.     }
    15.     if(tmp[l]==target)return true;
    16.     return false;
    17. }
    18. ll solve(){
    19.     cin>>n;
    20.     for(int i = 0;i
    21.         cin>>tmp[i];
    22.     }
    23.     if(n==1)return 0;
    24.     ll ans = 0,maxcnt=0;
    25.     for(int i = 0;i
    26.         if(tmp[n-1]+tmp[n-2]>=mol[i])maxcnt=i;
    27.         else break;
    28.     }
    29.     for(int i = 0;i-1;i++){
    30.         for(int j = 0;j<=maxcnt;j++){
    31.             if(mol[j]>2*tmp[i]){
    32.                 if(get(i+1,mol[j]-tmp[i]))ans++;
    33.             }
    34.         }
    35.     }
    36.     return ans;
    37. }
    38. int main() {
    39.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    40.     int t;
    41.     cin>>t;
    42.     mol[0] = 2;
    43.     for (int i = 1;; i++) {
    44.         mol[i] = mol[i - 1] * 2;
    45.         cnt++;
    46.         if (mol[i] > 2 * 1e9)break;
    47.     }
    48.     while (t--) {
    49.         cout<<solve()<<"\n";
    50.     }
    51.     return 0;
    52. }

    5.1553数字

    这题真就是典型的看着难，其实处理很简单。。。

    附上我做这题的心理路线和草稿

    最后这种想法的由来就是直接根据一个数，求它自己是不是合理数其实很快，但又不能提前将1e9以内的数一次性全判断完，那么每次就暴力查找它附近的数，反而成了最优解

    1. #include
    2. using namespace std;
    3. int main() {
    4.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    5.     int t;
    6.     cin>>t;
    7.     while(t--){
    8.         int n;
    9.         cin>>n;
    10.         while(1){
    11.             int x = n,cn=0;
    12.             while(x){
    13.                 cn+=x%10;
    14.                 x/=10;
    15.             }
    16.             if(n%cn==0){
    17.                 cout<"\n";
    18.                 break;
    19.             }
    20.             n--;
    21.         }
    22.     }
    23.     return 0;
    24. }

    6.1559奇偶数位

    简单的模拟题，暴力按顺序取，然后不断循环直到只有1位break

    记得看清楚题，不要读错题了像我一样还tle，wa。。。

    1. #include
    2. using namespace std;
    3. int main() {
    4.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    5.     int t;
    6.     cin >> t;
    7.     while (t--) {
    8.         int ans = 0;
    9.         string n;
    10.         cin>>n;
    11.         while(n.size()>1){
    12.             int s = n.size(),a=0,b=0;
    13.             for(int i = 0;i
    14.                 if(i&1)a=a*10+n[i]-'0';
    15.                 else b=b*10+n[i]-'0';
    16.             }
    17.             n = to_string(a*b);
    18.             ans++;
    19.         }
    20.         cout << ans << "\n";
    21.     }
    22.     return 0;
    23. }

    7.1575四位数

    四位数取出来排序，双指针取正反向的值，然后对结果进行取模赋值，简单的模拟

    1. #include
    2. #include
    3. using namespace std;
    4. const int mod = 10000;
    5. bool check(string x){
    6.     if(x[0]==x[1] && x[1] == x[2] && x[2] == x[3])return true;
    7.     return false;
    8. }
    9. int main() {
    10.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    11.     int t;
    12.     cin >> t;
    13.     while (t--) {
    14.         int ans = 0;
    15.         string var;
    16.         cin >> var;
    17.         while (!check(var)) {
    18.             int n[4];
    19.             for(int i =0;i<4;i++)n[i] = var[i]-'0';
    20.             sort(n,n+4);
    21.             ans++;
    22.             int a = 0, b = 0;
    23.             for (int i = 0; i < 4; i++) {
    24.                 a = a * 10 + n[i];
    25.                 b = b * 10 + n[3 - i] ;
    26.             }
    27.             int next = (a+b)%mod;
    28.             for(int i = 3;i>=0;i--){
    29.                 var[i] = next%10 + '0';
    30.                 next/=10;
    31.             }
    32.         }
    33.         cout<"\n";
    34.     }
    35.     return 0;
    36. }

    8.1530Game

    游戏模拟：可以将一局游戏分为三个部分

    1.开始：判断当前游戏是否开始（一个标记）（如果未开始则需要输出）

    2.判断结果：判断当前游戏是否分出胜负（一个标记）（未分出胜负要输出change，分出了的话在下一步输出，所以还要一个标记）

    3.结束：结束了要输出谁赢（并且将当前游戏是否开始标记为false）

    1. #include
    2. #include
    3. using namespace std;
    4. string player[2]={"Alice","Bob"};
    5. char op[4][10];
    6. int trans(){
    7.     int ans = 0;
    8.     for(int i = 0;i<4;i++){
    9.         if(op[i][0] == 'P')ans+=5;
    10.     }
    11.     return ans;
    12. }
    13. void start(string x,int n){
    14.     cout<" start game "<"\n";
    15. }
    16. void sayWinner(string x,int n){
    17.     cout<" win game "<"\n";
    18. }
    19. void sayChange(string x){
    20.     cout<<"Change to "<"\n";
    21. }
    22. void sayEnd(int a,int b){
    23.     cout<<"Game over "<":"<"\n";
    24. }
    25. int main() {
    26.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    27.     bool isend = true,isstart = false;
    28.     int cnt = 1;// 游戏局数
    29.     int cnta=0,cntb=0;
    30.     string winner = "Alice",nowSayer = "Alice";//赢家开始
    31.     int num;
    32.     while(scanf("%d%s%s%s%s",&num,op[0],op[1],op[2],op[3])!=EOF){
    33.         int now = trans();
    34.         if(!isstart){
    35.             start(winner,cnt);
    36.             isstart = true;
    37.             isend = false;
    38.         }
    39.         if(now == num){
    40.             winner = nowSayer;
    41.             if(nowSayer==player[0])cnta++;
    42.             else cntb++;
    43.             sayWinner(winner,cnt);
    44.             cnt++;
    45.             isend = true;
    46.             isstart = false;
    47.         }
    48.         if(!isend){
    49.             if(nowSayer == player[0])nowSayer = player[1];
    50.             else nowSayer = player[0];
    51.             sayChange(nowSayer);
    52.         }
    53.     }
    54.     sayEnd(cnta,cntb);
    55.     return 0;
    56. }

    9.1538打字机

    简单模拟，string比较好做，有erase和insert这种现成的函数

    主要思路还是用一个下标模拟光标进行移动和增删

    1. #include
    2. #include
    3. using namespace std;
    4. char buff[550];
    5. int main() {
    6.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    7.     while (scanf("%s", buff) != EOF) {
    8.         string ans;
    9.         int p = 0;//模拟光标
    10.         for (int i = 0; buff[i] != '\0'; i++) {
    11.             char v = buff[i];
    12.             if ((v >= 'a' && v <= 'z') || (v >= 'A' && v <= 'Z'))ans.insert(p++,1,v);
    13.             switch (v) {
    14.             case '[':
    15.                 p = 0;break;
    16.             case ']':
    17.                 p = ans.size();break;
    18.             case '<':
    19.                 if(p-1>=0)p--;break;
    20.             case '>':
    21.                 if(p+1<=ans.size())p++;break;
    22.             case '-':
    23.                 if(p-1>=0)ans.erase(--p,1);break;
    24.             case '+':
    25.                 if(p+1<=ans.size())ans.erase(p,1);break;
    26.             }
    27.         }
    28.         cout<'\n';
    29.     }
    30.     return 0;
    31. }

    10.1539区间

    这应该是前面十道题里比较需要思考的枚举题了

    需要对区间这个概念比较敏感，能知道对于某一特定区间，知道端点下标就能取到该区间内某个数

    那么自然就会想到用前缀和计算某一区间内包含字母的个数，对于一特定字母：用完整区间的个数减掉该区间就是剩下的个数

    这里我一开始是没想到前缀和的，毕竟很久没做过和区间有关的题了，看了谢大的思路后用O(n²)水过了，但是对于某一区间，我们长度从1枚举到***的时间复杂度肯定不如直接二分。

    但其实二分也有一点小处理，因为我们直接枚举长度没法包含所有左右端点的情况，所以枚举一个端点，而另一个端点用二分查找，通过端点的距离也可以算出当前的长度

    所以参考了另一位同学的做法，将600+ms的通过时间优化到了30ms

    1. #include
    2. #include
    3. using namespace std;
    4. int v[1010][26];
    5. int main() {
    6.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    7.     int t;
    8.     cin >> t;
    9.     while (t--) {
    10.         memset(v, 0, sizeof v);
    11.         int k, ans;
    12.         string tmp;
    13.         cin >> k >> tmp;
    14.         int n = tmp.size(), cnt = 0;
    15.         ans = n;
    16.         for (int i = 0; i < n; i++) {
    17.             v[i][tmp[i] - 'a']++;
    18.             if (i > 0)for (int j = 0; j < 26; j++)v[i][j] += v[i - 1][j];
    19.         }
    20.         for (int i = 0; i < 26; i++) {
    21.             if (v[n - 1][i] > k)cnt++;
    22.         }
    23.         if (cnt == 0)cout << "0\n";
    24.         else {
    25.             for (int l = 0; l < n; l++) {
    26.                 for (int r = l; r < n; r++) {
    27.                     bool fair = true;
    28.                     for (int i = 0; i < 26; i++) {
    29.                         int now = v[n - 1][i] - v[r][i];
    30.                         if (l > 0)now += v[l - 1][i];
    31.                         if (now > k) {
    32.                             fair = false;
    33.                             break;
    34.                         }
    35.                     }
    36.                     if (fair)ans = min(r - l + 1, ans);
    37.                 }
    38.             }
    39.             cout << ans << "\n";
    40.         }
    41.     }
    42.     return 0;
    43. }
    1. #include
    2. #include
    3. using namespace std;
    4. int v[1010][26],k,n;
    5. bool check(int l,int r){
    6. 	for (int i = 0; i < 26; i++) {
    7. 		int now = v[n - 1][i] - v[r][i];
    8. 		if (l > 0)now += v[l - 1][i];
    9. 		if (now > k) {
    10. 			return false;
    11. 		}
    12. 	}
    13. 	return true;
    14. }
    15. int main() {
    16. 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    17. 	int t;
    18. 	cin >> t;
    19. 	while (t--) {
    20. 		memset(v, 0, sizeof v);
    21. 		int ans;
    22. 		string tmp;
    23. 		cin >> k >> tmp;
    24. 		n = tmp.size();
    25. 		int cnt = 0;
    26. 		ans = n;
    27. 		for (int i = 0; i < n; i++) {
    28. 			v[i][tmp[i] - 'a']++;
    29. 			if (i > 0)for (int j = 0; j < 26; j++)v[i][j] += v[i - 1][j];
    30. 		}
    31. 		for (int i = 0; i < 26; i++) {
    32. 			if (v[n - 1][i] > k)cnt++;
    33. 		}
    34. 		if (cnt == 0)cout << "0\n";
    35. 		else {
    36. 			for(int i = 0;i// 枚举左端点
    37. 				int r = n-1,l = i;
    38. 				while(l<=r){ // 二分查找右端点
    39. 					int mid = (l+r)>>1;
    40. 					if(check(i,mid))r = mid-1;
    41. 					else l = mid+1;
    42. 				}//最终的查找结果为l
    43. 				if(check(i,l))ans = min(ans,l-i+1);
    44. 			}
    45. 			cout << ans << "\n";
    46. 		}
    47. 	}
    48. 	return 0;
    49. }

    11.1541卷积

    题目的两个3*3矩阵卷积应该比较容易看懂，但是可能1<=n,m这个比较困惑

    为什么原矩阵都没有3*3大小也能呢？其实题目中那句话很重要：

    为了保持原矩阵的维度，向外扩一圈0。这个其实就保证了以原矩阵元素为中心，一定存在对应的3*3大小矩阵用来和过滤矩阵做卷积。接下来就是模拟了，我没思考优化的点，毕竟时限也不小

    1. #include
    2. #include
    3. using namespace std;
    4. int buff[300][300], n, m, trans[3][3];
    5. int work(int s, int e) {
    6.     int sum = 0;
    7.     for (int i = s; i <= s + 2; i++) {
    8.         for (int j = e; j <= e + 2; j++) {
    9.             sum += buff[i][j] * trans[i - s][j - e];
    10.         }
    11.     }
    12.     if (sum > 255) sum = 255;
    13.     if (sum < 0 ) sum = 0;
    14.     return sum;
    15. }
    16. void solve() {
    17.     for (int i = 1; i <= n; i++) {
    18.         for (int j = 1; j <= m; j++) {
    19.             cout<< work(i - 1, j - 1);
    20.             if(j" ";
    21.         }
    22.         cout<<"\n";
    23.     }
    24. }
    25. int main() {
    26.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    27.     int t;
    28.     cin >> t;
    29.     while (t--) {
    30.         cin >> n >> m;
    31.         memset(buff, 0, sizeof buff);
    32.         for (int i = 1; i <= n; i++) {
    33.             for (int j = 1; j <= m; j++)cin >> buff[i][j];
    34.         }
    35.         for (int i = 0; i < 3; i++) {
    36.             for (int j = 0; j < 3; j++)cin >> trans[i][j];
    37.         }
    38.         solve();
    39.         cout<<"\n";
    40.     }
    41.     return 0;
    42. }

    12.1547圆

    不会证明，直接猜结论，因为排除了在弦内侧的情况，那么最特殊的点就是OC的反向延长线与圆的交点，也就是弦AB中垂线与圆的另一个交点，那么就是简单的勾股定理化简运算了

    1. #include
    2. using namespace std;
    3. int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
    4. int main() {
    5. 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    6. 	int t;
    7. 	cin >> t;
    8. 	while(t--){
    9. 		int r,h;
    10. 		cin>>r>>h;
    11. 		int mod = gcd(r,2*r+2*h);
    12. 		cout<'/'<<(2*r+2*h)/mod<<"\n";
    13. 	}
    14. 	return 0;
    15. }

    13.1576分段

    一句话题意：逆天中的逆天，居然又是枚举，又是因子

    这题自己做的时候脑海中无数的二分，贪心的叠加式，还写了个很二笔的暴力

    其实考虑过累加和，也考虑过子段和的k倍必是累加和，额就是没想到直接验证累加和的所有因子

    1. #include
    2. using namespace std;
    3. int arr[100100], n, all, ans;
    4. bool check(int a) {
    5. 	int var = 0;
    6. 	for (int i = 0; i < n; i++) {
    7. 		var += arr[i];
    8. 		if (var == a)var = 0;
    9. 		if (var > a)return false;
    10. 	}
    11. 	if (var && var != a)return false;
    12. 	return true;
    13. }
    14. int main() {
    15. 	scanf("%d", &n);
    16. 	for (int i = 0; i < n; i++) {
    17. 		scanf("%d", &arr[i]);
    18. 		all += arr[i];
    19. 	}
    20. 	ans = all; // 初始化为累加和
    21. 	if (n == all) { // 单列最小子段和为1的情况，那样下面的循环直接从2开始枚举因子
    22. 		ans = 1;
    23. 	} else {
    24. 		for (int i = 2; i * i <= all; i++) {
    25. 			if (all % i == 0) {
    26. 				if (check(i)) { // 一旦 check(i)有结果，那他一定是最小的，根据因子大小排布规律可知
    27. 					ans = i;
    28. 					break;
    29. 				} else if (check(all / i))ans = all / i; // 因为all/i是递减的，所以这里如果有结果，要取min就直接取当前结果即可
    30. // 但是这里不能break，因为小于sqrt(all)的那边还没check完
    31. 			}
    32. 		}
    33. 	}
    34. 	printf("%d\n", ans);
    35. 	return 0;
    36. }

    14.1583彩球

    典型的滑动窗口题，判断右端新增颜色y之后，now[y]是否为1，以及左端删除颜色x之后，now[x]是否为0，来维护当前总颜色数量cnt

    1. #include
    2. #include
    3. using namespace std;
    4. int n,m,k;
    5. int ball[10010];
    6. int now[10010];
    7. void sayno(){
    8. 	cout<<"No\n";
    9. }
    10. void sayyes(){
    11. 	cout<<"Yes\n";
    12. }
    13. int main() {
    14. 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    15. 	int t;
    16. 	cin>>t;
    17. 	while(t--){
    18. 		memset(now,0,sizeof now);
    19. 		cin>>n>>m>>k;
    20. 		for(int i = 0;i
    21. 			cin>>ball[i];
    22. 		}
    23. 		int l = 0,r = 0,cnt = 0;
    24. 		while(r-l+1<=m){
    25. 			if(now[ball[r]] == 0)cnt++;
    26. 			now[ball[r]]++;
    27. 			r++;
    28. 		}
    29. 		if(cnt!=k)sayno();
    30. 		else{
    31. 			bool sign = true;
    32. 			while(r
    33. 				int old_color = ball[l++],add_color = ball[r++];
    34. 				if(--now[old_color] == 0)cnt--;
    35. 				if(++now[add_color] == 1)cnt++;
    36. 				if(cnt!=k){
    37. 					sign = false;
    38. 					sayno();
    39. 					break;
    40. 				}
    41. 			}
    42. 			if(sign)sayyes();
    43. 		}
    44. 	}
    45. 	return 0;
    46. }

    15.1484刷油漆

    这道题也不是正常的模拟题，因为实际要满足时间复杂度的做法是要逆着输入的方向做。。。

    （这题也是美美打开题解了）

    注意这几点就能很好理解谢大的思路了：

    1.后涂过的行或者列会覆盖先涂的

    2.逆序遍历时，当前涂产生的颜色格子数（如果是涂行，那就是没被涂过的列数；如果是涂列，就是没被涂过的行数）

    3.输入的颜色c其实就是最终结果的值是在1~c之间，直接for循环遍历即可

    4.血的教训：输入到了1e4以上的规模时不会写快读就不要用cin和cout，关闭同步流也很影响时间

    1. #include
    2. using namespace std;
    3. int n, m, c, t;
    4. int op[100010][3];
    5. bool col[10010] = {0}, line[10010] = {0};
    6. int ans[1010]={0};
    7. int main() {
    8. 	scanf("%d%d%d%d",&n,&m,&c,&t);
    9. 	for (int i = 0; i < t; i++) {
    10. 		scanf("%d%d%d",&op[i][0],&op[i][1],&op[i][2]);
    11. 	}
    12. 	int rest_line = n, rest_col = m;
    13. 	for (int i = t - 1; i >= 0; i--) {
    14. 		if (op[i][0] == 1 && !col[op[i][1]]) {
    15. 			ans[op[i][2]] += rest_line;
    16. 			rest_col --;
    17. 			col[op[i][1]] = 1;
    18. 		} else if (op[i][0] == 0 && !line[op[i][1]]) {
    19. 			ans[op[i][2]] += rest_col;
    20. 			rest_line--;
    21. 			line[op[i][1]] = 1;
    22. 		}
    23. 	}
    24. 	for(int i = 1;i<=c;i++){
    25. 		if(ans[i])printf("%d %d\n",i,ans[i]);
    26. 	}
    27. 	return 0;
    28. }

    16.1556和

    收到前面对于区间的感触，对于一个区间特定值的查询可以转化为前缀和的方法

    这里矩阵其实处理办法也相同，只不过是将数组arr[i][j]看作是(1,1)~(i,j)的总面积，那么要求特定

    (i1,j1)~(i2,j2)的面积其实就是arr[i2][j2] - arr[i1-1][j2] - arr[i2][j1-1] + arr[i1-1][j1-1]

    这里自己画下图就可以理解

    然后是对于数据的预处理，在构造数组的时候是需要根据题意取模的，而我们求前缀是不需要的，而且构造的时候需要乘a，b啥的，所以我们求前缀和不能与构造并行，如果并行会导致后续的构造结果出错

    1. #include
    2. using namespace std;
    3. const int maxn = 1010;
    4. int n, m, a, b ,p , q;
    5. int buff[maxn][maxn]={0};
    6. void build(){
    7. 	// 初始化边界
    8. 	for(int i = 1;i<=n;i++)buff[i][1] = 1;
    9. 	for(int i = 1;i<=m;i++)buff[1][i] = 1;
    10. 	//根据题意构造
    11. 	for(int i = 2;i<=n;i++){
    12. 		for(int j = 2;j<=m;j++){
    13. 			buff[i][j] = (a*buff[i-1][j] + b*buff[i][j-1])%p;
    14. 		}
    15. 	}
    16. 	//求前缀和，因为2的这一列写法不一样，我就单独写了两个循环，避免反复的if判断减少耗时
    17. 	for(int i = 2;i<=m;i++)buff[1][i] = buff[1][i]+buff[1][i-1];
    18. 	for(int i = 2;i<=n;i++)buff[i][1] = buff[i][1]+buff[i-1][1];
    19. 	for(int i = 2;i<=n;i++){
    20. 		for(int j = 2;j<=m;j++){
    21. 			buff[i][j] = buff[i][j]+buff[i-1][j]+buff[i][j-1]-buff[i-1][j-1];
    22. 		}
    23. 	}
    24. }
    25. int main() {
    26. 	int t;
    27. 	scanf("%d",&t);
    28. 	while(t--){
    29. 		scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&p,&q);
    30. 		build();
    31. 		for(int i = 1;i<=q;i++){
    32. 			int i1,i2,j1,j2;
    33. 			scanf("%d%d%d%d",&i1,&j1,&i2,&j2);
    34. 			int ans = buff[i2][j2] - buff[i2][j1-1] - buff[i1-1][j2] + buff[i1-1][j1-1];
    35. 			printf("%d\n",ans);
    36. 		}
    37. 		printf("\n");
    38. 	}
    39. 	return 0;
    40. }

    17.1560平方数

    对于给定方程求解的情况，给出的参数尽量分离出来，将未知的全部放到一起，并且尽量写成乘积的形式，那样等式右边就是给定的一个常数，而左边是一个多项式乘积，将左边每个括号看作一个因子，然后根据括号内的内容反解出x的表达式

    （只要我们求出因子，那每个因子都对应一个括号整体的值，那我们完全可以将一个括号看做一个新的常数，从而根据几个等式联立求出x的解）

    这里也是看上题解了，但是真的很难想到方程的构造方法，但确实每次遇到都是这类做法，

    一句话总结：菜！就多练！

    一些写代码时要注意的点：

    1.原方程的分类讨论条件中不要使用除法，（比如b*b-4*c > 0，如果写成b*b/4 - c > 0可能会造成误差）

    2.题解思路中说到的两种情况（大于小于0）一定要分开求，因为解的形式是不同的，而且对应求的谁的因子也不一样

    3.注意题目中说的x是大于0的整数。（不然outputlimitexceed）

    4.注意从小到大输出

    1. #include
    2. #include
    3. using namespace std;
    4. int cnt;
    5. int ans[10000];
    6. int main() {
    7. 	int t;
    8. 	scanf("%d", &t);
    9. 	while (t--) {
    10. 		cnt = 0;
    11. 		int b, c;
    12. 		scanf("%d%d", &b, &c);
    13. 		int res = 4 * c - b * b;
    14. 		if (res == 0) {
    15. 			printf("-1\n");
    16. 			continue;
    17. 		} else if (res > 0) {
    18. 			int var = res;
    19. 			for (int i = 1; i * i <= var; i++) {
    20. 				if (var % i == 0) {
    21. 					int p = i, q = var / i;
    22. 					if ((q - p - 2 * b) / 4 > 0 && (q - p - 2 * b) % 4 == 0)ans[cnt++] = (q - p - 2 * b) / 4;
    23. 				}
    24. 			}
    25. 		} else {
    26. 			int var = res * (-1);
    27. 			for (int i = 1; i * i <= var; i++) {
    28. 				if (var % i == 0) {
    29. 					int p = i, q = var / i;
    30. 					if ((p + q - 2 * b) / 4 > 0 && (p + q - 2 * b) % 4 == 0)ans[cnt++] = (p + q - 2 * b) / 4;
    31. 				}
    32. 			}
    33. 		}
    34. 		if (cnt == 0)printf("0\n");
    35. 		else {
    36. 			sort(ans, ans + cnt);
    37. 			for (int i = 0; i < cnt; i++) {
    38. 				while(i+11] == ans[i])i++;
    39. 				printf("%d", ans[i]);
    40. 				if (i + 1 < cnt)printf(" ");
    41. 				else printf("\n");
    42. 			}
    43. 		}
    44. 	}
    45. 	return 0;
    46. }

    18.1567三个矩形和一个正方形

    这个枚举题一开始确实不知道从何下手，谢大的思路还是很独特，实现也比较简单

    要构成正方形一定可以拆分为先拿两个构成新矩形，再用新矩形去构造结果矩形（这个矩形如果两边相等即为正方形，用谢大思路如果面积为平方数好像也行）

    1. #include
    2. using namespace std;
    3. int matrix[3][2];
    4. int pre[2]; // a为第一个合成矩形中的公共边，b为两个小矩形拼接成的新边
    5. bool check(int x,int y){// 拿下标非x非y的那一个矩形与prea,preb进行check
    6. 	int k;
    7. 	for(int i = 0;i<3;i++)if(i!=x && i!=y)k = i;
    8. 	for(int i = 0;i<2;i++){
    9. 		for(int j = 0;j<2;j++){
    10. 			if(matrix[k][i] == pre[j]){
    11. 				if(matrix[k][i] == matrix[k][(i+1)%2] + pre[(j+1)%2])return true;
    12. 			}
    13. 		}
    14. 	}
    15. 	return false;
    16. }
    17. bool solve(){
    18. 	for(int i = 0;i<2;i++){
    19. 		for(int j = 0;j<3;j++){
    20. 			if(i == j)continue;
    21. 			for(int k = 0;k<2;k++){
    22. 				for(int p = 0;p<2;p++){
    23. 					if(matrix[i][k] == matrix[j][p]){
    24. 						pre[0] = matrix[i][k];
    25. 						pre[1] = matrix[i][(k+1)%2] + matrix[j][(p+1)%2];
    26. 						if(check(i,j))return true;
    27. 					}
    28. 				}
    29. 			}
    30. 		}
    31. 	}
    32. 	return false;
    33. }
    34. int main() {
    35. 	int t;
    36. 	scanf("%d",&t);
    37. 	while(t--){
    38. 		for(int i = 0;i<3;i++)scanf("%d%d",&matrix[i][0],&matrix[i][1]);
    39. 		if(solve())printf("Yes\n");
    40. 		else printf("No\n");
    41. 	}
    42. 	return 0;
    43. }

    19.1578拼图

    暴力递归检索四个拼图的排序状态

    按顺时针方向先先检查单向对接情况，最后检查第一个和第四个的对接状况

    1. #include
    2. #include
    3. using namespace std;
    4. char chosse[4][2];
    5. char str[4][5];
    6. bool ans, vis[4];
    7. bool check(char a, char b) {
    8. 	if (a - 'a' == b - 'A' || a - 'A' == b - 'a')return true;
    9. 	return false;
    10. }
    11. void dfs(int cnt) {
    12. 	// 顺时针放置顺序  1(0) (1)2
    13. 	//			·	 (1)     (0)
    14. 	//          	 (0)	 (1)
    15. 	//				  4(1) (0)3
    16. 	if (ans)return ;
    17. 	if (cnt == 4) { // 四个拼图顺时针已符合，只差第四个和第一个的首尾拼接
    18. 		if (check(chosse[0][1], chosse[3][0]))ans = true;
    19. //		for(int i = 0;i<=3;i++)printf("%c_%c ",chosse[i][0],chosse[i][1]);
    20. //		printf("\n");
    21. 		return ;
    22. 	}
    23. 	for (int i = 0; i < 4; i++) {
    24. 		if (vis[i])continue;
    25. 		vis[i] = true;
    26. 		for (int j = 0; j < 4; j++) {
    27. 			// 第一个放不需要检查配对性
    28. 			// 检查配对性，当前的（j+1）%4号位要对上前一个chosse的0号位
    29. 			if (cnt == 0 || check(str[i][(j + 1) % 4], chosse[cnt - 1][0])) {
    30. 				chosse[cnt][0] = str[i][j];
    31. 				chosse[cnt][1] = str[i][(j + 1) % 4];
    32. 				dfs(cnt + 1);
    33. 			}
    34. 		}
    35. 		vis[i] = false;
    36. 	}
    37. }
    38. int main() {
    39. 	int t;
    40. 	scanf("%d", &t);
    41. 	while (t--) {
    42. 		memset(vis, false, sizeof vis);
    43. 		ans = false;
    44. 		for (int i = 0; i < 4; i++)scanf("%s", str[i]);
    45. 		dfs(0);
    46. 		if (ans)printf("Yes\n");
    47. 		else printf("No\n");
    48. 	}
    49. 	return 0;
    50. }

    20.1565MarkDown表格

    这题是真的坑，虽然数据是符合题意，但有点不符合常理，总结一下所有要注意的点

    1. 表头硬性居中
    2. 第二行的排版方式字符串不计入该列最长字符串长度
    3. 一格中的数据会带有空格（其中前后多余空格不计）
    4. 第二行的字符串可以直接取头取尾直接判断属于哪一类
    5. 相邻两个|之间的字符串可能为纯空格，要将它等效替换为一个空格字符用来占位
    6. 最后一个底线输出完有换行（也就是整个表中三次输出底线都有换行）
    1. #include
    2. using namespace std;
    3. string str[15][15];
    4. int maxn[15] = {0};
    5. int way[15] = {0}; // 记录每列的排版方式，用0/1/2区分
    6. int n;
    7. void print_empty(int cnt) { // 输出空格数
    8. 	for (int i = 1; i <= cnt; i++)cout << " ";
    9. }
    10. void print_width(int cnt ) { // 输出边线中的'-'
    11. 	for (int i = 1; i <= cnt; i++)cout << "-";
    12. }
    13. void print_head() { // 输出头
    14. 	cout << "|";
    15. 	for (int i = 0; i < n; i++) {
    16. 		int all = maxn[i] + 2; // 当前列宽
    17. 		int all_empty = all - str[0][i].size();
    18. 		print_empty(all_empty / 2);
    19. 		cout << str[0][i];
    20. 		print_empty(all_empty - all_empty / 2);
    21. 		cout << "|";
    22. 	}
    23. 	cout << "\n";
    24. }
    25. void print_v() { // 输出完整边线
    26. 	cout << "+";
    27. 	for (int i = 0; i < n; i++) {
    28. 		print_width(maxn[i] + 2);
    29. 		cout << "+";
    30. 	}
    31. 	cout << "\n";
    32. }
    33. void print_unit(int cnt_line) { // 根据列数输出单元格的行，从2开始（0为头，1为排版方式）
    34. 	cout << "|";
    35. 	for (int i = 0; i < n; i++) {
    36. 		int all = maxn[i] + 2;
    37. 		int all_empty = all - str[cnt_line][i].size();
    38. 		if (way[i] == 0) {
    39. 			print_empty(1);
    40. 			cout << str[cnt_line][i];
    41. 			print_empty(all_empty - 1);
    42. 		} else if (way[i] == 2) {
    43. 			print_empty(all_empty - 1);
    44. 			cout << str[cnt_line][i];
    45. 			print_empty(1);
    46. 		} else {
    47. 			print_empty(all_empty / 2);
    48. 			cout << str[cnt_line][i];
    49. 			print_empty(all_empty - all_empty / 2);
    50. 		}
    51. 		cout << "|";
    52. 	}
    53. 	cout << "\n";
    54. }
    55. int main() {
    56. 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    57. 	string input;
    58. 	int line = 0;
    59. 	while (getline(cin, input)) {
    60. 		int cnt = 0; // 当前列号
    61. 		string var;
    62. 		for (int i = 0; i < input.size(); i++) {
    63. 			char x = input[i];
    64. 			if (x == '|') { // 读到 | 进行一次记录
    65. 				int p = var.size() - 1;
    66. 				while (var[p] == ' ')var.erase(p--, 1);
    67. 				if (var.size() == 0)var = " ";
    68. //				var.erase(var.find_last_not_of(" ") + 1);
    69. 				str[line][cnt] = var;
    70. 				if (line != 1)maxn[cnt] = max(maxn[cnt], (int)var.size()); // 更新cnt列的最大长度
    71. 				cnt++;
    72. 				var.clear();
    73. 			} else if (x == ' ' && !var.empty())var += x; // 不统计前置空格
    74. 			else if (x != '|' && x != ' ')var += x; //统计非空格，非|的字符
    75. 		}
    76. 		// 统计最后一个字符
    77. 		int p = var.size() - 1;
    78. 		while (var[p] == ' ')var.erase(p--, 1);
    79. 		if (var.size() == 0)var = " ";
    80. 		str[line][cnt] = var;
    81. 		if (line != 1)maxn[cnt] = max(maxn[cnt], (int)var.size()); // 更新cnt列的最大长度
    82. 		cnt++;
    83.  
    84. 		n = cnt; // 如果样例每行都是相同列数，n为列数
    85. 		line++;
    86. 	}
    87. 	for (int i = 0 ; i < n; i++) {
    88. 		string now = str[1][i]; // 第二行为排版方式字符串
    89. 		bool f1 = false, f2 = false;
    90. 		f1 = now[0] == ':';
    91. 		f2 = now[now.size() - 1] == ':';
    92. 		if ((f1 && f2) || (!f1 && !f2))way[i] = 1;
    93. 		else if (f1)way[i] = 0;
    94. 		else way[i] = 2;
    95. 	}
    96. 	for(int i = 0;i
    97. 		for(int j = 0;j
    98. 			cout<size()<<"^^^";
    99. 		}
    100. 		cout<<"\n";
    101. 	}
    102. 	print_v();
    103. 	print_head();
    104. 	print_v();
    105. 	for (int i = 2; i < line; i++)print_unit(i);
    106. 	print_v();
    107. 	return 0;
    108. }
  • 相关阅读:
    Linux内存管理（六）：内存模型SPARSEMEM初始化
    useState源码解读 及 手撕 useState 实现
    不同数据库行号关联问题
    数组指针的使用
    Stream流式处理
    微前端：qiankun的依赖import-html-entry的作用
    jsp+ssm+maven美容院管理系统--idea mysql
    PyCharm 虚拟环境搭建
    [性能优化] 使用 esbuild 为你的构建提速
    小红书2022上半年品牌营销数据报告
  • 原文地址：https://blog.csdn.net/G_yyyy/article/details/137287947