代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <stack> 5 #include <queue> 6 #include <deque> 7 #include <cmath> 8 #include <string> 9 #include <vector> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <sstream> 14 #include <iostream> 15 #include <algorithm> 16 //#include <unordered_map> 17 #define INF 0x3f3f3f3f 18 #define ll long long 19 #define ull unsigned long long 20 #define FILL(a,n,v) fill(a,a+n,v) 21 #define Mset(a,v) memset(a,v,sizeof a) 22 #define Mcpy(a,b) memcpy(a,b,sizeof b) //a=b 23 #define fcio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) 24 using namespace std; 25 const int maxn=1e5; 26 27 int t; 28 int n; 29 30 bool isprime(int x) 31 { 32 if(x<=1) return false; 33 for(int i=2;i*i<=x;i++) 34 { 35 if(x%i==0) return false; 36 } 37 return true; 38 } 39 40 int main() 41 { 42 cin>>t; 43 while(t--) 44 { 45 cin>>n; 46 if(isprime(n)) 47 { 48 for(int i=0;i<n;i++) 49 { 50 for(int j=0;j<n;j++) 51 { 52 cout<<1<<(j==n-1?‘\n‘:‘ ‘); 53 } 54 } 55 } 56 else 57 { 58 int t=1; 59 while(1) 60 { 61 t++; 62 if(!isprime(t)&&isprime(t+n-1)) break; 63 } 64 65 for(int i=0;i<n;i++) 66 { 67 for(int j=0;j<n;j++) 68 { 69 if(i==j) cout<<t<<(j==n-1?‘\n‘:‘ ‘); 70 else cout<<1<<(j==n-1?‘\n‘:‘ ‘); 71 } 72 } 73 } 74 } 75 }
差分数组+思维
有一个长度为n的数组a。你可以进行无数次如下操作：
问能否使数组中的元素全部变成0
转化成一个差分问题。(假设差分数组为ans)要使数组中的全部数都为0，那么差分数组也必须为0且ans[1]=0。
那么我们来看两种操作对于差分数组有何影响：
操作1：ans[1]-1 且ans[i+1]+1。那么我们就可以凭借操作1，将差分数组中的负数变成0，同时减小ans[1]。
操作2：ans[i+1]-1且ans[n+1]+1。那么我们就可以凭借操作2，将差分数组中的正数变成0，而ans[n+1]为多少和我们并没有关系。
在最开始时ans[1]=a[1]，所以只要差分数组的负数和的绝对值小于等于a[1],即输出YES，否则输出NO。
因为如果差分数组的负数和的绝对值大于a[1],那么要使后面的数都变成0，ans[1]就会变成负数，而并没有使ans[1]由负数变成0的操作，操作2只能使ans[1]由正数变成0，所以这样并不满足要求。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <stack> 5 #include <queue> 6 #include <deque> 7 #include <cmath> 8 #include <string> 9 #include <vector> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <sstream> 14 #include <iostream> 15 #include <algorithm> 16 //#include <unordered_map> 17 #define INF 0x3f3f3f3f 18 #define ll long long 19 #define ull unsigned long long 20 #define FILL(a,n,v) fill(a,a+n,v) 21 #define Mset(a,v) memset(a,v,sizeof a) 22 #define Mcpy(a,b) memcpy(a,b,sizeof b) //a=b 23 #define fcio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) 24 #define fcin freopen("in.txt","r",stdin) 25 #define fcout freopen("out.txt","w",stdout) 26 using namespace std; 27 const int maxn=1e5+10; 28 int t; 29 int n; 30 int a[maxn]; 31 int d[maxn]; 32 33 int main() 34 { 35 // fcin; 36 fcio; 37 cin>>t; 38 while(t--) 39 { 40 cin>>n; 41 for(int i=1;i<=n;i++) cin>>a[i]; 42 d[1]=a[1]; 43 for(int i=2;i<=n;i++) d[i]=a[i]-a[i-1]; 44 45 int sum=0; 46 for(int i=2;i<=n;i++) if(d[i]<0) sum-=d[i]; 47 48 if(sum>d[1]) cout<<"NO"<<endl; 49 else cout<<"YES"<<endl; 50 } 51 return 0; 52 53 }
原文：https://www.cnblogs.com/lihahahahaji/p/13939054.html