|
目錄 T1：CF1276C Beautiful Rectanglesolution 保證不重復(fù)，我們就按對(duì)角線這樣填下去就可以了，這個(gè)很好想到
但注意行，列的變換不要這么寫(xiě)，因?yàn)榭赡苁翘厥獾恼叫?/p>
r = ( r 1 ) % row;
c = ( c 1 ) % col;
接下來(lái)返回考慮怎樣確定這個(gè)矩陣的大小\(row,col\)，要求\(row<=col\)
我們可以暴力枚舉\(row\)
也就是說(shuō)每一個(gè)數(shù)的最多出現(xiàn)次數(shù)要求一定小于等于\(row\)，不然肯定有一行會(huì)有重復(fù)數(shù)字
然后我們把這些數(shù)字出現(xiàn)次數(shù)加起來(lái)，就能計(jì)算出列
注意在判斷矩陣大小的時(shí)候必須\(row*col\)來(lái)判斷，不能單純按統(tǒng)計(jì)的數(shù)字最多出現(xiàn)次數(shù)
因?yàn)椴灰欢苷齖(row\)，所以有些數(shù)不一定達(dá)到了上限的 code#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 400005
vector < pair < int, int > > g;
vector < vector < int > > ans;
vector < int > num;
int n, row, col;
int a[MAXN], b[MAXN], cnt[MAXN];
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i )
scanf( "%d", &a[i] ), b[i] = a[i];
sort( a 1, a n 1 );
int m = unique( a 1, a n 1 ) - a - 1;
for( int i = 1;i <= n;i ) b[i] = lower_bound( a 1, a m 1, b[i] ) - a;
for( int i = 1;i <= n;i ) cnt[b[i]] ;
for( int i = 1;i <= m;i ) g.push_back( make_pair( cnt[i], i ) );
sort( g.begin(), g.end() );
int now = 0;
for( int i = 1;i <= sqrt( n );i ) {
int temp = 0;
for( int j = 0;j < g.size();j )
temp = min( g[j].first, i );
if( temp / i < i ) continue;
else if( temp / i * i > now ) now = temp / i * i, row = i, col = temp / i;
}
printf( "%d\n%d %d\n", row * col, row, col );
reverse( g.begin(), g.end() );
for( int i = 0;i < g.size();i ) {
for( int j = 1;j <= min( g[i].first, row );j )
num.push_back( g[i].second );
}
ans.resize( row );
for( int i = 0;i < row;i ) ans[i].resize( col );
int r = 0, c = 0;
for( int i = 0;i < num.size();i ) {
ans[r][c] = num[i];
r , c ;
if( r == row ) r = 0, c -= row - 1;
if( c < 0 ) c = col;
if ( c >= col ) c -= col;
}
for( int i = 0;i < row;i ) {
for( int j = 0;j < col;j )
printf( "%d ", a[ans[i][j]] );
printf( "\n" );
}
return 0;
}
T2：CF226D The tablesolution本質(zhì)就是個(gè)暴力
對(duì)于總和小于零的每一行，每一列都進(jìn)行取反操作即可
當(dāng)某一行或某一列操作次數(shù)為偶數(shù)的時(shí)候，其實(shí)相當(dāng)于是無(wú)效操作，最后輸出答案的時(shí)候判掉即可
為什么這么暴力就可以？——因?yàn)槲覀兿拗屏瞬僮鞯目偞螖?shù)極限就是\(1e6\)
把每一行和每一列的和加起來(lái)等于整個(gè)矩陣的總和的兩倍，值域\([-4e6,4e6]\)
每次取反至少是\(-1=>1\)，整個(gè)矩陣總和的兩倍至少增加\(4\)，當(dāng)和無(wú)法再增加的時(shí)候就是每一行每一列都大于零 code#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 105
vector < int > r, c;
int n, m;
int row[MAXN], col[MAXN], visr[MAXN], visc[MAXN];
int a[MAXN][MAXN];
int main() {
scanf( "%d %d", &n, &m );
for( int i = 1;i <= n;i )
for( int j = 1;j <= m;j ) {
scanf( "%d", &a[i][j] );
row[i] = a[i][j];
col[j] = a[i][j];
}
while( 1 ) {
bool flag = 1;
for( int i = 1;i <= n;i )
if( row[i] < 0 ) {
visr[i] ;
row[i] = - row[i];
for( int j = 1;j <= m;j )
col[j] -= ( a[i][j] << 1 ), a[i][j] = - a[i][j];
flag = 0;
break;
}
for( int i = 1;i <= m;i )
if( col[i] < 0 ) {
visc[i] ;
col[i] = - col[i];
for( int j = 1;j <= n;j )
row[j] -= ( a[j][i] << 1 ), a[j][i] = - a[j][i];
flag = 0;
break;
}
if( flag ) break;
}
for( int i = 1;i <= n;i )
if( visr[i] & 1 ) r.push_back( i );
for( int i = 1;i <= m;i )
if( visc[i] & 1 ) c.push_back( i );
printf( "%d", r.size() );
for( int i = 0;i < r.size();i )
printf( " %d", r[i] );
printf( "\n%d", c.size() );
for( int i = 0;i < c.size();i )
printf( " %d", c[i] );
return 0;
}
T3：CF549G Happy Linesolution非常巧的一個(gè)點(diǎn)——對(duì)于第\(i\)個(gè)數(shù)，不管它以后的位置在哪，它原來(lái)的下標(biāo)\(i\)值與\(val\)的和是個(gè)定值
所以貪心就想到總和越大的越應(yīng)該往后放
這樣才有可能不減
如果有一個(gè)數(shù)\(i\)的總和大于最后一個(gè)數(shù)的總和且在前面某個(gè)位置，那么數(shù)\(i\)的值就等于總和減去現(xiàn)在的下標(biāo)，本來(lái)值就比最后一個(gè)大，減去的又比最后一個(gè)小，自然就不可能成為不減序列 code#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 200005
struct node {
int val, id;
}v[MAXN];
int n;
bool cmp( node x, node y ) {
return x.val x.id < y.val y.id;
}
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i )
scanf( "%d", &v[i].val ), v[i].id = i;
sort( v 1, v n 1, cmp );
for( int i = 1;i <= n;i )
if( v[i].id v[i].val == v[i - 1].id v[i - 1].val )
return ! printf( ":(" );
else if( i > v[i].id v[i].val ) return ! printf( ":(");
for( int i = 1;i <= n;i )
printf( "%d ", v[i].id v[i].val - i );
return 0;
}
T4：CF798D Mike and distributionsolution\[2*\sum_{i=1}^xa[p[i]]>\sum_{j=1}^na[j],2*\sum_{i=1}^xb[p[i]]>\sum_{j=1}^nb[j]
\] 不管是\(a\)還是\(b\)數(shù)組，都減去一倍已選的數(shù)
其實(shí)最后的要求都轉(zhuǎn)化為了，\(a,b\)數(shù)組已選的數(shù)的和要大于沒(méi)選的數(shù)的和
從\(\lfloor \frac{n}{2}\rfloor 1\)這個(gè)特別要求入手
考慮分奇偶討論
當(dāng)\(n=2k\)
按\(a\)的從大到小排序，并兩兩分組
第一組的全選上，之后的每一組選擇\(b\)較大的一個(gè)
接下來(lái)證明這個(gè)算法的正確性
我們每一組都選的\(b\)較大的一個(gè)，自然可以壓制另一個(gè)的\(b\)，\(b\)的要求已經(jīng)達(dá)到
那么\(a\)怎么辦呢?
如果較大的\(b\)的\(a\)也較大，那自然更好，甭考慮
如果是較小的\(a\)，也不用害怕，因?yàn)槲覀兊谝唤M的兩個(gè)\(a\)都選了
它們一定大于這一組里面較大的\(a\)，可以壓制
那么后面遇到類似情況怎么辦，最大的兩個(gè)\(a\)已經(jīng)用了，沒(méi)關(guān)系
兩個(gè)\(a\)用了，一定解救出前面較大的某些（個(gè)）\(a\)，拿來(lái)壓制現(xiàn)在的\(a\)
就這么一個(gè)一個(gè)壓制下去，最后讓\(a\)也達(dá)到要求
奇數(shù)同理可得，不再重復(fù) code#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 100005
struct node {
int a, b, id;
}v[MAXN];
int n;
bool cmp( node x, node y ) {
return x.a > y.a;
}
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i )
scanf( "%d", &v[i].a ), v[i].id = i;
for( int i = 1;i <= n;i )
scanf( "%d", &v[i].b );
sort( v 1, v n 1, cmp );
printf( "%d\n", ( n >> 1 ) 1 );
if( n % 2 ) {
printf( "%d ", v[1].id );
for( int i = 2;i <= n;i = 2 )
if( v[i].b > v[i 1].b ) printf( "%d ", v[i].id );
else printf( "%d ", v[i 1].id );
}
else {
printf( "%d %d ", v[1].id, v[2].id );
for( int i = 3;i <= n;i = 2 )
if( v[i].b > v[i 1].b ) printf( "%d ", v[i].id );
else printf( "%d ", v[i 1].id );
}
return 0;
}
T5：CF351E Jeff and Permutationsolution考慮數(shù)\(a,b\)，且\(|a|>|b|\)
①\(a\)取\( \)
如果\(b\)在\(a\)前面，不管\(b\)取\(±\)都不會(huì)有逆序?qū)?br>如果\(b\)在\(a\)后面，不管\(b\)取\(±\)都會(huì)有逆序?qū)?br>②\(a\)取\(-\)
如果\(b\)在\(a\)前面，不管\(b\)取\(±\)都不會(huì)有逆序?qū)?br>如果\(b\)在\(a\)后面，不管\(b\)取\(±\)都會(huì)有逆序?qū)?/p> 我們發(fā)現(xiàn)，逆序?qū)Φ漠a(chǎn)生只與兩個(gè)數(shù)的相對(duì)位置以及較大數(shù)的正負(fù)有關(guān) 所以我們只需要考慮對(duì)于下標(biāo)為\(i\)的數(shù)，前面絕對(duì)值比他小的有多少個(gè)，后面比他小的有多少個(gè)，取個(gè)\(min\)即可
至于比他大的數(shù)自然是交個(gè)比他大的數(shù)來(lái)管他們之間是否會(huì)有逆序?qū)?，不管這個(gè)數(shù)取正取負(fù)，逆序?qū)Χ荚谳^大數(shù)的決定上
所以彼此是相互獨(dú)立的，不會(huì)造成影響 那么兩個(gè)數(shù)的絕對(duì)值一樣的時(shí)候呢？這個(gè)時(shí)候的正負(fù)不就有影響了嗎？
所以我們?cè)摱x一個(gè)\(dp[i][j]:\)前\(i\)個(gè)數(shù)有\(zhòng)(j\)個(gè)為\(-\)，然后進(jìn)行轉(zhuǎn)移
其實(shí)并不需要，可以證明絕對(duì)值一樣的數(shù)一定會(huì)是前面一段全選負(fù)后面一段全是正
假設(shè)下標(biāo)\(i<j\)且\(|a[i]|=|a[j]|\)
如果\(i\)選了正，意味著數(shù)列\(zhòng)([1,i)\)個(gè)絕對(duì)值比\(i\)小的個(gè)數(shù)多于\((i,n]\)的個(gè)數(shù)
那么\(j\)而言，前面的數(shù)已經(jīng)包含了\([1,i)\)，還多加了一段\((i,j)\)，那么前面絕對(duì)值小于它的數(shù)個(gè)數(shù)只會(huì)增加（不變）不會(huì)減小，后面\((j,n]\)則只會(huì)減?。ú蛔儯┎粫?huì)增大
所以是不會(huì)彼此之間產(chǎn)生逆序?qū)Φ模凑丈厦婷總€(gè)數(shù)獨(dú)立判斷的做法做即可 code#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define MAXN 2005
int n, ans;
int p[MAXN];
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i )
scanf( "%d", &p[i] );
for( int i = 1;i <= n;i ) {
int Left = 0, Right = 0;
for( int j = 1;j < i;j )
if( fabs( p[i] ) <= fabs( p[j] ) ) continue;
else Left ;
for( int j = i 1;j <= n;j )
if( fabs( p[i] ) <= fabs( p[j] ) ) continue;
else Right ;
ans = min( Left, Right );
}
printf( "%d", ans );
return 0;
}
T6：CF1148E Earth Wind and Firesolution很常規(guī)的貪心思想，按值排序后，然后下標(biāo)一一對(duì)應(yīng)，即\(s[i]\)負(fù)責(zé)成為\(t[i]\)
然后我們從最大的開(kāi)始往下判斷，要知道\(s\)一定先把多余的可以傳遞的傳遞給臨近的
因?yàn)槿绻鸤(i\)把多余的分給離他很遠(yuǎn)的\(s[j]\)，則\(s[j]<=s[i 1]\)
就算加上了\(s[i]\)給的\(x\)，\(s[j],s[i 1]\)之間的差距也不如將\(x\)分給\(s[i 1]\)優(yōu)
差距越大能傳遞的\(d\)越大
同時(shí)傳遞后要保證\(s[i]>=t[i]\)，當(dāng)循環(huán)到某一個(gè)數(shù)后，發(fā)現(xiàn)他的\(s<t\)，則無(wú)解
因?yàn)槲覀儚拇蟮叫∫灰粠头鲞^(guò)來(lái)
此時(shí)的數(shù)一定接受了比他大的所有的數(shù)多出來(lái)的\(t[]-s[]\)
全加上也沒(méi)到要求
后面的數(shù)也幫不了它，因?yàn)閈(s[該數(shù)]>=s[后面的數(shù)]\)，無(wú)法進(jìn)行轉(zhuǎn)移 code#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 300005
#define int long long
struct node {
int val, id;
}s[MAXN], t[MAXN];
struct noded {
int l, r, val;
noded( int L, int R, int V ) {
l = L, r = R, val = V;
}
};
vector < noded > ans;
int n, sums, sumt;
bool cmp( node x, node y ) {
return x.val > y.val;
}
signed main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i ) {
scanf( "%d", &s[i].val );
s[i].id = i, sums = s[i].val;
}
for( int i = 1;i <= n;i ) {
scanf( "%d", &t[i].val );
t[i].id = i, sumt = t[i].val;
}
if( sums != sumt ) return ! printf( "NO" );
sort( s 1, s n 1, cmp );
sort( t 1, t n 1, cmp );
int last = 1;
for( int i = 1;i <= n;i ) {
if( s[i].val < t[i].val ) return ! printf( "NO" );
while( s[i].val > t[i].val ) {
while( t[last].val <= s[last].val ) last ;
int temp;
temp = min( t[last].val - s[last].val, s[i].val - t[i].val );
temp = min( temp, ( s[i].val - s[last].val ) >> 1 );
s[i].val -= temp, s[last].val = temp;
ans.push_back( noded( s[last].id, s[i].id, temp ) );
}
}
printf( "YES\n%d\n", ans.size() );
for( int i = 0;i < ans.size();i )
printf( "%lld %lld %lld\n", ans[i].l, ans[i].r, ans[i].val );
return 0;
}
來(lái)源：https://www./content-4-723401.html
|
