A Crossmarket
思维
矩阵走路径，发现走Z字型怎么走都是一样的耗费，所以直接O(1)算出来就好
/** |~~~~~~~|* | |* | |* | |* | |* | |* |~.\\\_\~~~~~~~~~~~~~~xx~~~ ~~~~~~~~~~~~~~~~~~~~~/_//;~|* | \ o \_ ,XXXXX), _..-~ o / |* | ~~\ ~-. XXXXX`)))), _.--~~ .-~~~ |* ~~~~~~~`\ ~\~~~XXX' _/ ';)) |~~~~~~..-~ _.-~ ~~~~~~~* `\ ~~--`_\~\, ;;;\)__.---.~~~ _.-~* ~-. `:;;/;; \ _..-~~* ~-._ `'' /-~-~* `\ / /* | , | |* | ' / |* \/; |* ;; |* `; . |* |~~~-----.....|* | \ \* | /\~~--...__ |* (| `\ __-\|* || \_ /~ |* |) \~-' |* | | \ '* | | \ :* \ | | |* | ) ( )* \ /; /\ |* | |/ |* | | |* \ .' ||* | | | |* ( | | |* | \ \ |* || o `.)|* |`\\) |* | |* | |*/ #include<iostream> #include<queue> #include<vector> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<unordered_map> #include<unordered_set> #include<set> #include<map> // #pragma GCC optimize(3) using namespace std; #define rep(i,x,y) for(int i=x;i<y;i++) #define scan(x) scanf("%lld",&x) #define int long long #define lowbit(x) x&(-x) //二进制最低位所代表的数 #define PI 3.1415926535 typedef pair<int,int> PII; int gcd(int a,int b){return b>0 ? gcd(b,a%b):a; } int exgcd(int a,int b,int &x,int &y) {if(!b){x = 1,y = 0;return a;}int d = exgcd(b,a%b,y,x);y-=a/b*x;return d; } const int N = 1e6+10; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; void init() {cin.tie(0),cout.tie(0);ios::sync_with_stdio(false); }void solve() {int n,m;cin>>n>>m;if(n<m)swap(n,m);if(n==1&&m==1){cout<<0<<endl;return;}int t = n+(m-2)+2+(m-2);cout<<t<<endl; }signed main() {init();int t;cin>>t;while(t--)solve(); }
B Beautiful a Array
构造
放k*b就满足了“漂亮”性质，然后还要每个都加上min(s,k-1)来满足总数和的性质
/** |~~~~~~~|* | |* | |* | |* | |* | |* |~.\\\_\~~~~~~~~~~~~~~xx~~~ ~~~~~~~~~~~~~~~~~~~~~/_//;~|* | \ o \_ ,XXXXX), _..-~ o / |* | ~~\ ~-. XXXXX`)))), _.--~~ .-~~~ |* ~~~~~~~`\ ~\~~~XXX' _/ ';)) |~~~~~~..-~ _.-~ ~~~~~~~* `\ ~~--`_\~\, ;;;\)__.---.~~~ _.-~* ~-. `:;;/;; \ _..-~~* ~-._ `'' /-~-~* `\ / /* | , | |* | ' / |* \/; |* ;; |* `; . |* |~~~-----.....|* | \ \* | /\~~--...__ |* (| `\ __-\|* || \_ /~ |* |) \~-' |* | | \ '* | | \ :* \ | | |* | ) ( )* \ /; /\ |* | |/ |* | | |* \ .' ||* | | | |* ( | | |* | \ \ |* || o `.)|* |`\\) |* | |* | |*/ #include<iostream> #include<queue> #include<vector> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<unordered_map> #include<unordered_set> #include<set> #include<map> // #pragma GCC optimize(3) using namespace std; #define rep(i,x,y) for(int i=x;i<y;i++) #define scan(x) scanf("%lld",&x) #define int long long #define lowbit(x) x&(-x) //二进制最低位所代表的数 #define PI 3.1415926535 typedef pair<int,int> PII; int gcd(int a,int b){return b>0 ? gcd(b,a%b):a; } int exgcd(int a,int b,int &x,int &y) {if(!b){x = 1,y = 0;return a;}int d = exgcd(b,a%b,y,x);y-=a/b*x;return d; } const int N = 1e6+10; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; void init() {cin.tie(0),cout.tie(0);ios::sync_with_stdio(false); }void solve() {int n,k,b,s;cin>>n>>k>>b>>s;vector<int> a(n);a[0]=k*b;s-=k*b;if(s<0){cout<<-1<<endl;return;}for(int i=0;i<n;i++){int t = min(s,k-1);a[i]+=t;s-=t;}if(s>0){cout<<-1<<endl; }else{for(int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;} }signed main() {init();int t;cin>>t;while(t--)solve(); }
C Monoblock
数学规律
这种查询题就是先找出最终结果然后进行减法操作，这样才不会超时。
所以这道题的触发是换之后是否相等，相等的话那么会进行减法，减去有这两个元素的区间，不相等的话加上。
子区间( i )*( n - i )
/** |~~~~~~~|* | |* | |* | |* | |* | |* |~.\\\_\~~~~~~~~~~~~~~xx~~~ ~~~~~~~~~~~~~~~~~~~~~/_//;~|* | \ o \_ ,XXXXX), _..-~ o / |* | ~~\ ~-. XXXXX`)))), _.--~~ .-~~~ |* ~~~~~~~`\ ~\~~~XXX' _/ ';)) |~~~~~~..-~ _.-~ ~~~~~~~* `\ ~~--`_\~\, ;;;\)__.---.~~~ _.-~* ~-. `:;;/;; \ _..-~~* ~-._ `'' /-~-~* `\ / /* | , | |* | ' / |* \/; |* ;; |* `; . |* |~~~-----.....|* | \ \* | /\~~--...__ |* (| `\ __-\|* || \_ /~ |* |) \~-' |* | | \ '* | | \ :* \ | | |* | ) ( )* \ /; /\ |* | |/ |* | | |* \ .' ||* | | | |* ( | | |* | \ \ |* || o `.)|* |`\\) |* | |* | |*/ #include<iostream> #include<queue> #include<vector> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<unordered_map> #include<unordered_set> #include<set> #include<map> // #pragma GCC optimize(3) using namespace std; #define rep(i,x,y) for(int i=x;i<y;i++) #define scan(x) scanf("%lld",&x) #define int long long #define lowbit(x) x&(-x) //二进制最低位所代表的数 #define PI 3.1415926535 typedef pair<int,int> PII; int gcd(int a,int b){return b>0 ? gcd(b,a%b):a; } int exgcd(int a,int b,int &x,int &y) {if(!b){x = 1,y = 0;return a;}int d = exgcd(b,a%b,y,x);y-=a/b*x;return d; } const int N = 1e6+10; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; void init() {cin.tie(0),cout.tie(0);ios::sync_with_stdio(false); }int a[N];void solve() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}int cnt = 0;int sum = 0; for(int i=1;i<=n;i++){if(a[i]!=a[i-1])cnt+=i;else cnt++;sum+=cnt;}while(m--){int i,x;cin>>i>>x;if(a[i-1]!=a[i]&&a[i-1]==x){sum-=(i-1)*(n-i+1);}if(a[i-1]==a[i]&&a[i-1]!=x){sum+=(i-1)*(n-i+1);}if(a[i+1]!=a[i]&&a[i+1]==x){sum-=(i)*(n-i);}if(a[i+1]==a[i]&&a[i+1]!=x){sum+=(i)*(n-i);}a[i]=x;cout<<sum<<endl;} }signed main() {init();int t=1;while(t--)solve(); }
